As we know, studiyng differences between uniform complexity and nonuniform complexity class is crucial.

For example, P/poly is defined as challenges to derive a separation between P and NP, because P/poly and superpoly-circuit lower bounds gives us the separation.

However, it is possible that P/poly is NOT appropriate to measure the computational ability of uniform P which is defined by usual Turing Machine.

Circuits, branching programs, protocol trees are considerd as physical devices rather than computer programs. Physical devices force to increase the number of "input wires" and can we produce infinitely many devices (and these devices are able to be very very different as the nubmer of input wires increases ) by constant length bit-strings ? It seems that both questions have the answer "NO".

Thus my question is :

(1)Is there any nonuniform (relating with circuits or branching programs) complexity classe C that contains P but P/poly contains the class C.

(2)What is the complexity class which satisfies (1) and is colosest to P as far we know ?

  • $\begingroup$ P/1, or even P itself. $\endgroup$ – Kaveh Feb 28 '13 at 15:54
  • $\begingroup$ @Kaveh: I think the OP is asking about "truly nonuniform" classes, say defined in terms of some computational device (e.g. circuit, branching program, etc.) that is defined separately for each input length. P is most definitely uniform (not nonuniform), and although P/1 is a mix of uniform and nonuniform, it is not nonuniform in the above sense (it still requires the uniform polytime TM that takes 1 bit of nonuniform advice). The characterization of P/poly in terms of circuit families, one circuit for each length, makes it "truly nonuniform." Perhaps wenly can clarify. $\endgroup$ – Joshua Grochow Feb 28 '13 at 17:10
  • $\begingroup$ @wenly: I don't understand what you mean by the sentences "P/poly is defined as challenges to derive a separation between P and NP" and "everyone trying to prove general circuit lower bounds crushes the notourious barrier named Natural Proofs." These don't seem crucial to the question, however, so it might be better just to remove them...If I've understood correctly, the question is really: "is there some truly nonuniform model (as in my previous comment) that more closely captures (uniform) P than P/poly does?" $\endgroup$ – Joshua Grochow Feb 28 '13 at 17:12
  • 2
    $\begingroup$ (1) Perhaps Bounded deterministic constraint logic (0 player) games model; it is P-complete (through circuit simulation) and obviously contained in P/poly $\endgroup$ – Marzio De Biasi Feb 28 '13 at 20:17
  • 1
    $\begingroup$ @MarzioDeBiasi: Ah, yes. Now that I've looked more into that paper... If you look at their Theorem 1 it is clear that if you use Bounded DCL to define a "constraint graph family" (Bounded DCL is to constraint graph family as Circuit Value Problem is to circuit family), and then leave the edges corresponding to the input un-set, then their same proof shows that this model is exactly as powerful as P/poly. $\endgroup$ – Joshua Grochow Mar 1 '13 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.