<p>Theorem 2.2 in "<a href="http://www.sciencedirect.com/science/article/pii/030439759200014I" rel="nofollow">Nondeterministic circuits, space complexity and quasigroups</a>", by Wolf, 1994 (a technical report version is available <a href="ftp://128.105.2.31/pub/techreports/1989/TR870.pdf" rel="nofollow">here</a> without fee), proves that NP = NNC, where NNC is the class of languages decidable by an L-uniform family of nondeterministic NC circuits. A <em>nondeterministic NC circuit</em> is an NC circuit with a polynomial number of nondeterministic input bits. The simulation essentially guesses a tableau of an arbitrary NP machine then verifies that each configuration proceeds from the previous one according to the transition function of the machine. My interpretation of this proof is that the NC circuit is in fact an NC<sup>1</sup> circuit, since it simply takes the conjunction of a polynomial number of subcircuits, each of which checks that a local "window" in the tableau is valid.</p>

<p>Assuming that interpretation is correct, it should follow that NP = NL, since NC<sup>1</sup> is in L, so the same argument will apply. What is the error in my interpretation of this result? Why doesn't the strategy "guess a tableau, verify that each configuration follows from the previous" work?</p>

CC BY-SA 3.0
2015-10-30T21:42:50.643Z
NC¹, even in its nonuniform version, cannot guess a polynomial number of bits.  In NNC, the guessing part is entirely decoupled from the circuit part.
Michaël Cadilhac
CC BY-SA 3.0
2015-10-30T21:56:40.027Z
$NP = \exists FO = \exists^P AC^0$. You can actually drop it even to depth $AC^0_2$. The whole point of this is that verification is not the difficult part, the difficult part is nondeterminism. If you want to get rid of the nondeterministic bits, you essentially need to do an exponential size disjunction.
Kaveh
CC BY-SA 3.0
2015-10-31T11:31:20.670Z
Unlike the N (really $\exists$, as written in Kaveh's comment) from the definition of NNC, the N in NL does not allow you to record the sequence of nondeterministic choices and reinspect it later (apart from logarithmically many bits that fit within the space quota). This is what makes the difference.
Emil Jeřábek
CC BY-SA 3.0
2015-11-05T15:07:19.680Z
@EmilJeřábek So the model for NL computation is not equivalent to $\exists w \colon (x, w) \in R$, where $R$ is a language decidable in logarithmic space?
argentpepper
CC BY-SA 3.0
2015-11-05T15:14:25.357Z
No, it’s not equivalent. The latter is just NP again.
Emil Jeřábek
<cc.complexity-theory><complexity-classes>
Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?
argentpepper
# Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?

(Asked by: username_0 on 2015-10-30)

Theorem 2.2 in "[Nondeterministic circuits, space complexity and quasigroups](http://www.sciencedirect.com/science/article/pii/030439759200014I)", by Wolf, 1994 (a technical report version is available [here](ftp://128.105.2.31/pub/techreports/1989/TR870.pdf) without fee), proves that NP = NNC, where NNC is the class of languages decidable by an L-uniform family of nondeterministic NC circuits. A *nondeterministic NC circuit* is an NC circuit with a polynomial number of nondeterministic input bits. The simulation essentially guesses a tableau of an arbitrary NP machine then verifies that each configuration proceeds from the previous one according to the transition function of the machine. My interpretation of this proof is that the NC circuit is in fact an NC1 circuit, since it simply takes the conjunction of a polynomial number of subcircuits, each of which checks that a local "window" in the tableau is valid.

Assuming that interpretation is correct, it should follow that NP = NL, since NC1 is in L, so the same argument will apply. What is the error in my interpretation of this result? Why doesn't the strategy "guess a tableau, verify that each configuration follows from the previous" work?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: NC¹, even in its nonuniform version, cannot guess a polynomial number of bits.  In NNC, the guessing part is entirely decoupled from the circuit part.  
> **username_2**: $NP = \exists FO = \exists^P AC^0$. You can actually drop it even to depth $AC^0_2$. The whole point of this is that verification is not the difficult part, the difficult part is nondeterminism. If you want to get rid of the nondeterministic bits, you essentially need to do an exponential size disjunction.  
> **username_3**: Unlike the N (really $\exists$, as written in Kaveh's comment) from the definition of NNC, the N in NL does not allow you to record the sequence of nondeterministic choices and reinspect it later (apart from logarithmically many bits that fit within the space quota). This is what makes the difference.  
> **username_0**: @EmilJeřábek So the model for NL computation is not equivalent to $\exists w \colon (x, w) \in R$, where $R$ is a language decidable in logarithmic space?  
> **username_3**: No, it’s not equivalent. The latter is just NP again.  

---

## 0 answers

