So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. It seems like this is the exact same as being able to verify that a result is correct in polynomial time, but not necessarily solve the problem in polynomial time. Both these ideas make sense, but these ideas seem very different to me. One is talking about solvability of a problem in a nondeterministic context while the other is talking about solvability vs. verifiability. Can you please intuitively explain why they're related, and if this relationship between solvability, verifiability, determinism, nondeterminism applies to harder complexity classes such as EXP vs NEXP?
1 Answer
Here's some intuition for the equivalence proof
$(\implies)$: Suppose we have a non-deterministic Turing Machine $M$ that solves a problem $P$ in polynomial time. When we run $M$ on some accepted input $x$, we make a bunch of decisions non-deterministically, essentially choosing an execution path. If we record each of those choices, this gives is a string with is polynomial in the size of $x$ (since we know $M$ runs in non-deterministic polynomial time). Then the trace of running $M$ on $x$, with each decision point, is a certificate for $x$. We can follow the steps again and check that any string represents a valid run on $M$, and see whether it ends in a YES or NO state.
$(\impliedby)$: Suppose we have a verifier which takes a string $c$ and input $x$ and checks if $c$ is a valid certificate that $x$ is accepted by problem $P$, where $|c| \leq |x|^k$ for some fixed $k$. Then we can make an NTM which looks at any $x$ and determines whether it is in $P$ by "guessing" non-deterministically guessing a certifier $c$ of length less than $|x|^k$ and running the verifier on that.
EDIT: to apply this to $EXP$ and $NEXP$, just replace the word polynomial with exponential and change the bound on $c$, and the rest should still work. It doesn't really apply to classes like $PSPACE$, since it's not defined in terms of non-deterministic machines. Not being able to make these kinds of guesses are what makes PSPACE harder (as far as we know) than NP.
-
$\begingroup$ Thanks for your help! I understand your first part of the equivalence. I don't understand the backwards implication. I get that $c \leq |x|^k$ because it's proportional only to a polynomial degree but I don't understand the part about making an NTM that looks at any $x$ etc. $\endgroup$– rb612Commented Jun 2, 2016 at 4:00
-
$\begingroup$ What don't you understand? Do you understand what NTMs are, and how they can use non-determinism to "guess" values? Another way of looking at it is, they try all possible certificates and see if your verifier succeeds on any of them. The non-determinism lets us do this in polynomial time. $\endgroup$ Commented Jun 2, 2016 at 4:12
-
$\begingroup$ Ah I think I get what you were trying to say now. Can you make sure I got my understanding right for the backwards implication? You have a verifier that can take $c$ and $x$ that will validate if it satisfies $P$. I'm assuming this runs in polynomial time because of the inequality. The NTM then finds a solution in polynomial time and the checker will run in polynomial time? So this amounts to polynomial time? Which would make sense. And then could you explain also if this extends to harder complexity classes such as EXP vs NEXP? $\endgroup$– rb612Commented Jun 2, 2016 at 4:20
-
1$\begingroup$ Re PSPACE, remember that, by Savitch's theorem, PSPACE=NPSPACE. $\endgroup$ Commented Jun 2, 2016 at 9:33
-
1$\begingroup$ PSpace is ATime(poly). But ATime allows conondeterministic branching as well as nondeterministic branching. Also note that PSpace = IP so there is a more general notion of polysize interactive proof that also works for PSpace, polysize noninteractive proofs for NP is a special case of that. $\endgroup$– KavehCommented Jun 2, 2016 at 11:18