"Equivalent device" for testing for NP and coNP?

Question

I'm trying to understand some aspects of the $P=^?NP$ and $NP=^?coNP$ problems.

I am engineer and not mathematician nor computer scientist so I do not completely understand what a turing machine is.

I'm currently thinking about a variant of the "subset sum problem" known to be in $NP$ and suspected to be not in $coNP$. However I'm thinking of a modified variant of the problem.

It is easy to prove that a computer based on a "real" CPU can prove the answer "yes, a subset exists" (when the subset is known) in less than $(n+a)^2$ operations (while $a$ depends on the type of CPU used) when the original set contains $n$ elements.

From my understanding of $NP$ this implies that the problem belongs to $NP$. My first question is if this understanding is correct.

(I write "belongs to $NP$" and not "$\in NP$" because I know I mix up terms like "problem", "formal language", ...)

I suspect the minimum number of operations (on the real CPU) to prove the answer "no, no matching subset exists" to be more than $\frac{2^n}b$ (while $b$ depends on the type of CPU used).

So my second question is if this would mean that the problem does not belong to $coNP$.

As far as I know that there are differences between Turing Machines and CPU-based computers:

• A Turing Machine has unlimited memory while a computer has limited memory
• A Turing Machine can't generate true (undeterministic) random numbers while on a computer you may use the noise of the microphone input...
• ...

So I'm not sure if "cannot be calculated by a computer in polynomal time" implies "cannot be calculated by a Turing Machine in polynomal time".

-- Edit --

Having read the answers I think I have to say something about the background of the question:

I think I had already understood what P, NP or coNP is before asking the question but I was not 100% sure because I was not sure about the differences between a Turing Machine and a computer.

I have an idea how it could be possible to prove the impossibility to build a digital computer that can solve a certain problem in less than $a^nb$ steps while $n$ is the number of inputs and $a$ and $b$ depends on the computer and the problem.

I was just wondering if such a proof was sufficient to prove $P \neq NP$ if it could be done for a problem that is known to be in NP.

Having read your answers I think that such a proof would be sufficient. Thanks.

(Needless to say that I am not able to carry the proof I'm thinking of for any problem.)

Answer 1

I will not directly answer your questions, as this would result in explaining the definitions of $\mathsf{NP}$ and $\mathsf{coNP}$, which has been done before. However, using the following hint combined with the definition of the complexity classes indirectly answers your questions.

---

A modern computer with unlimited memory is equivalent to the concept of a register machine, which in turn is turing equivalent. Thus everything that can be computed on a modern computer with infinite memory can also be computed by a turing machine and vice-versa.

A Turing Machine can't generate true (undeterministic) random numbers while on a computer you may use the noise of the microphone input...

A microphone, or any other hardware-based true random number generator, is an input of the computer. That means the values delivered by it are not computed by the computer itself. Note that you can also model random input by a two-tape turing machine, where one tape contains the random numbers.

Answer 2

P, NP, co-NP are all about "decision problems", that is problems where the answer is either "yes" or "no".

P is the set of problems that I can solve in polynomial time if the answer is "yes", and co-P is the set of problems that I can solve in polynomial time if the answer is "no". P and co-P are the same: If I can solve problems where the answer is "yes" in polynomial time, then I can solve problems where the answer is "no" also in polynomial time: I just try to prove that the answer is "yes", and if I fail for long enough time, then I know the answer must be "no" (because if it was "yes", I would have found the answer).

NP can be described in different ways. It is the set of problems where for every instance where the answer is "yes", there is a proof for that that can be checked in polynomial time. Alternatively, you can solve the problem in polynomial time if you have an unfailing ability to make lucky guesses. And co-NP is almost the same, except that it works when the answer is "no".

But here the situation is different. Take your problem: If I give you two subsets of equal size, you can easily check that a set can be split into two sets of equal size. But if there are no two sets of equal size - it seems very hard to prove that they don't exist. And I can't come up with the slightest idea what would help you to prove that the answer is no (quite obvious, because I would be really, really famous if I could).

On a lower level, the problem whether a number is composite. It's easy to prove if the answer is yes: I just give you a prime factor, and that's it. There is no obvious way to prove that the answer is "no" - but it turned out quite incredibly that there is indeed for every prime a short proof that it is prime that can be tested quite quickly; that required some deep mathematics. So "composite" is both in NP and in co-NP. There is a suspicion that the intersection of NP and co-NP is less than NP, and in fact a way to check primality or compositeness in polynomial time was found. (Unfortunately that method can prove that a number is composite, but it cannot find factors).

Answer 3

Complexity theory is based on analyzing the asymptotic running time of algorithms. In order to talk about asymptotics, the input length should be unbounded. However, real CPUs can only handle inputs of bounded length. So you cannot do complexity theory with real CPUs.

In more details, in complexity theory we only care about the order of growth of the running time; so running times of $n$ and $1000n$ are the same for us. Everything that can be computed at all on a real CPU can be computed in some finite time, so all problems computable on a real CPU have complexity $O(1)$.

One way out of this mess is to consider an idealized version of a real CPU which can handle arbitrary inputs. Such an ideal version would probably be very similar to a RAM machine, and these are known to be polynomial equivalent to Turing machines. Without getting into details, this means that you can define classes like $P,NP,coNP$ using a RAM machine instead of a Turing machine, and you'll get exactly the same class.

You mention that real CPUs have access to randomness. While randomness is considered in complexity theory, the complexity classes $P,NP,coNP$ assume machines with no access to randomness (deterministic machines), so you'll have to disallow this. If you really care about randomness, you should probably look into the complexity classes $BPP,AM,coAM$, which are one possible list of analogues of $P,NP,coNP$. (For AM, see this.)

Finally, you mention that you suspect that the minimum number of operations needed to certify a negative instance in the worst case scales like $2^n$. If the suspicion were true, then it would indeed follows that subset sum is not in $coNP$. Unfortunately, nobody knows how to prove this.