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.)