1
$\begingroup$

Theorem 2.2 in "Nondeterministic circuits, space complexity and quasigroups", by Wolf, 1994 (a technical report version is available here 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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Oct 30 '15 at 21:42
  • 3
    $\begingroup$ $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. $\endgroup$ – Kaveh Oct 30 '15 at 21:56
  • 4
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 31 '15 at 11:31
  • $\begingroup$ @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? $\endgroup$ – argentpepper Nov 5 '15 at 15:07
  • $\begingroup$ No, it’s not equivalent. The latter is just NP again. $\endgroup$ – Emil Jeřábek Nov 5 '15 at 15:14

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.