Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it is unclear how another NDTM $T$ can determine in $O(n^{100})$ time how to flip $M$’s answer.

My Problem is as follows: A NDTM outputs $1$ iff there exists a sequence of non-deterministic choices that leads to the accepting state. Furthermore, there exists a universal NDTM $NU$ that can simulate every NDTM with only a small (logarithmic) overhead. So why can’t we construct T as follows: First, simulate M with the universal NDTM which should be possible in time $O(n\log n)$. Then output 1 – M’s answer. This would mean that we can flip the answer of any linear NDTM in time $O(n\log n)$.

share|improve this question

3 Answers 3

up vote 10 down vote accepted

A nondeterministic Turing machine accepts if at least one path accepts; it only rejects if all paths reject. This asymmetry makes it hard to "flip answers".

For example, suppose you have a nondeterministic Turing machine $M$ that has two paths for input $w$: one accepts, the other rejects. $M$ has at least one accepting path for $w$, so it accepts. Suppose we want to produce a machine that accepts exactly the inputs that $M$ rejects. The obvious first attempt is to take $M$ and make its accepting states reject, and its rejecting states accept. $M$ has one accepting path for $w$ and one rejecting path; this new machine $M'$ has one rejecting path and one accepting path. So it still accepts $w$, which it was supposed to reject!

A nondeterministic machine can't look at all its paths simultaneously and take action based on what all of those paths do. If you like, you can think of it as a form of parallelism where the threads are forbidden to communicate with each other. When all of the threads have finished the program must ask itself the following question: "Did at least one of my threads accept?" If the answer is yes, it is legally obliged to accept; if the answer is no, it is legally obliged to reject. It cannot do anything else.

When you simulate a nondeterministic machine $M$ using another one, $M'$, each path of $M'$ simulates one path of $M$ and sees only that path. It can't say, "If all those other paths rejected, I'll accept" because it can't see the other paths; it can only see itself. So all it could possibly say is things like, "If the path I simulated accepted, I'll reject" or "If the path I simulated accepted, I'll accept too". Then, at the end of the computation, the machine has to say, "If any of my paths accepted, I'll accept too", leading to the problem I described above. To invert the behaviour of $M$, each path of $M'$ needs to say, "If the path I simulated accepted, I reject; else, I accept" and, at the end of the computation, the machine needs to say, "If all of my paths accepted, I accept; else, I reject." This is because, if all of the simulator's paths accepted, that means all of $M$'s paths rejected, so $M$ rejected, so the simulator needs to accept. But the simulator isn't a valid nondeterministic Turing machine because it isn't using the legally mandated acceptance criterion. It can't do that.

The only way we know to figure out if a nondeterministic machine rejects its input is to try every possible path and verify that they all reject. After all, if even one of them accepted, the machine would accept the input. But trying every possible path is exponentially slower than trying just one.

share|improve this answer

The problem is that NDTM are inherently non-symmetric: the time $O(n)$ means that they have $O(n)$ steps to guess an accepting path if exists, and will reject otherwise (if no accepting path exists).

The problem is that if your machine $NU$ is really in $O(n log( n))$, it means that it guesses in $n log (n)$ steps a witness that $M$ rejects the input. This might not be possible to do, because there are no witnesses of rejection of $M$, just witnesses of acceptance. Rejection is the absence of witness, so it is not easy to prove rejection in a short time.

share|improve this answer

actually technically you are asking the P$\stackrel{?}{=}$coNP($\stackrel{?}{=}$NP) question which is open. it is widely conjectured but not proven that they are not equal. the other answers are intuitive sketches/circumstantial evidence why they are not equal.

share|improve this answer
1  
Actually, he's asking something similar to co-NP=NP: it's perfectly possible that P and NP are different but NDTMs can be efficiently negated. –  David Richerby Feb 19 at 0:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.