NP vs co-NP

09 Sep 2014, 11:27 UTC

NP is the set of all languages that can be accepted by a non-deterministic Turing Machine (NTM) in polynomial time.

A language L is a set of strings S over some alphabet A. For instance, A could be ASCII and L could be "ASCII strings that are valid C++". If L is in NP, there exists an NTM X such that it can accept all strings S in L, with a strict upper bound on the number of steps it takes to halt given by u(#S), where u(N) is a polynomial in N.

The set A* is the set of all strings over alphabet A. A*\L is the set of suitable strings which are not in the language L, for instance, "ASCII strings that are not valid C++". Since L is in NP, A*\L is in co-NP - this is how co-NP is defined.

It is not known whether NP = co-NP, or not.

But suppose you run the NTM X on a string S from A*, and then you wait u(#S) steps. If the machine X has halted then S is in L. But since u(#S) is a strict upper bound, then if the machine has not halted, we know S is in A*\L (even though the machine hasn't told us anything, because it didn't halt).

The point being, the NTM has already done all the work necessary to prove that S is not in L. The only reason it can't tell us about it is because of some technicalities to do with how it's allowed to halt.

That is, the NTM as a whole halts whenever ANY of its subthreads halt, and all halting states are equivalent to "accept S". There is simply no concept of an NTM rejecting the string S. It doesn't go into a "reject S" state. It just never halts - NONE of its subthreads halt, which means effectively ALL of its subthreads reject S.

If the NTM was designed such that it could be configured to halt only when ALL of its subthreads halt, we could solve co-NP in polynomial time. The state "accept S" would enter an infinite loop. The paths where S is not accepted could time themselves, and halt when the time limit was reached. Then, if all paths halt, the machine as a whole halts, and we know S is in A*\L.

All this is moot because NTMs are not physically realizable, at least not using classical physics, but it shows that there is a metasystem in which NTMs are embedded in which NP' = co-NP', trivially (that metasystem can also be expressed as a DTM which monitors the NTM and times it - there is no need for human intervention, only a secondary DTM). This metasystem is very different to what we're used to - for instance, membership in NP' does *not* imply existence of a certificate in P'=P, because for the reject cases there is no single path through the NTM which can be replayed on a DTM; the proof involves all the paths.

But *morally* speaking the NTM for any L in NP has done all the work required to prove that S is not in L in the same amount of time it takes if it were to prove S is in L.

So what this result really shows is that NP per se has really got nothing to do with how much work an NTM can do in polynomial time, it has to do with what results of that work are able to be reported back to the user when the cross-thread "join" system is restricted to an ANY test rather than an ALL test or some other test. Obviously an NTM is way more powerful in principle than a DTM, but that's not what the question "is P = NP?" means.