<p>As we know, studiyng differences between uniform complexity and nonuniform complexity class is crucial. </p>

<p>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. </p>

<p>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. </p>

<p>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".   </p>

<p>Thus my question is :</p>

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

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

CC BY-SA 3.0
2013-02-28T15:54:16.707Z
P/1, or even P itself.
Kaveh
CC BY-SA 3.0
2013-02-28T17:10:11.780Z
@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.
Joshua Grochow
CC BY-SA 3.0
2013-02-28T17:12:28.287Z
@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?"
Joshua Grochow
CC BY-SA 3.0
2013-02-28T18:26:27.723Z
@Josh, maybe, but do we have a definition of what is a non-uniform complexity class (other than not being uniform)? So I think P/1 is a non-uniform class. It seems to me that any uniform class can be thought of as a non-uniform class, i.e. uniformity is an extra condition, non-uniform is used when the uniformity condition does not or is not *known* to hold.
Kaveh
CC BY-SA 3.0
2013-02-28T20:17:14.953Z
(1) Perhaps [Bounded deterministic constraint logic (0 player) games](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.184.8875&rep=rep1&type=pdf) model; it is P-complete (through circuit simulation) and obviously contained in P/poly
Marzio De Biasi
CC BY-SA 3.0
2013-02-28T21:51:19.600Z
@MarzioDeBiasi: make that an answer?
Joshua Grochow
CC BY-SA 3.0
2013-02-28T22:20:01.977Z
@JoshuaGrochow: ... mmm ... I'm still thinking if it can be considered a non-uniform model (a graph of size $n$ acts like a "circuit" and the "input" is realized through the target edge $e$ and unreversible edges $R_0$)
Marzio De Biasi
CC BY-SA 3.0
2013-03-01T01:40:03.803Z
@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.
Joshua Grochow
CC BY-SA 3.0
2013-03-01T03:31:41.670Z
Sentences about Natural Proofs make question unclear and even wrongful thus I would delete.
shen
CC BY-SA 3.0
2013-03-01T03:32:22.357Z
I think what  is coressponding to the circuits and branching programs and communicaiton protocol trees and other models which is very slightly powerful uniform-P.
shen
<cc.complexity-theory><complexity-classes><advice-and-nonuniformity>
Smallest Nonuniform Complexity Classes including uniform-P
shen
# Smallest Nonuniform Complexity Classes including uniform-P

(Asked by: username_0 on 2013-02-28)

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 ?

**Tags:** cc.complexity-theory, complexity-classes, advice-and-nonuniformity

> **Comments:**
> **username_1**: P/1, or even P itself.  
> **username_2**: @username_1: 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.  
> **username_2**: @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?"  
> **username_1**: @Josh, maybe, but do we have a definition of what is a non-uniform complexity class (other than not being uniform)? So I think P/1 is a non-uniform class. It seems to me that any uniform class can be thought of as a non-uniform class, i.e. uniformity is an extra condition, non-uniform is used when the uniformity condition does not or is not *known* to hold.  
> **username_3**: (1) Perhaps [Bounded deterministic constraint logic (0 player) games](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.184.8875&rep=rep1&type=pdf) model; it is P-complete (through circuit simulation) and obviously contained in P/poly  
> **username_2**: @MarzioDeBiasi: make that an answer?  
> **username_3**: @JoshuaGrochow: ... mmm ... I'm still thinking if it can be considered a non-uniform model (a graph of size $n$ acts like a "circuit" and the "input" is realized through the target edge $e$ and unreversible edges $R_0$)  
> **username_2**: @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.  
> **username_0**: Sentences about Natural Proofs make question unclear and even wrongful thus I would delete.  
> **username_0**: I think what  is coressponding to the circuits and branching programs and communicaiton protocol trees and other models which is very slightly powerful uniform-P.  

---

## 0 answers

