Here is a necessarily wrong proof of $P \neq NP$ as it relativizes, but I can't find the error :

Le $U$ be a universal Turing machine, whose inputs are restricted to Turing machines accepting languages in P. Let $L = \mathcal{L}(U)$ the language accepted by $U$, hence the acceptation language restricted to P.

  • L is in NP as for each instance where $\mathcal{L}(M) \in P$ and $x$ an input of $M$, the certificate of $x$ is a certificate for L too
  • L is not in P as it would be in $DTIME(n^k)$ for a fixed $k$ and as $DTIME(n^{m+1}) - DTIME(n^m) \neq \emptyset$, if we choose a M in $DTIME(n^{k+1})$ and fix it, U would decide the problem in $\mathcal{O}(n^k)$

You are being a little sloppy with your definitions: what exactly is the input to U, and what exactly are the conditions to accept? In particular, you probably need to include in the input to U not just a Turing machine but also a specific polynomial that bounds the running time of the machine, because otherwise it's undecidable whether any particular TM really is polynomial time. But that's not the real problem.

The actual problem is that L(U) is not in NP. To be in NP, there needs to be a single polynomial p(n) that bounds the time to check a solution. But in your case this time is bounded by a polynomial q(n) that depends on the particular TM given as input. It's easy to choose inputs that cause q(n) to be larger than any fixed choice of p(n).

  • $\begingroup$ In your last sentence, I assume you mean "inputs of U" and not "inputs of M" by "inputs" because the input x of M is part of the input of U (which takes <M,x> as input), so for a fixed M, if q(n) is an upper bound for M, it is for U. So If I understand, this is a proof that for each polynomial, there is a problem in P such as time to check solution isn't bounded by this polynomial. $\endgroup$ – Ludovic Patey Sep 5 '10 at 8:38

"Le U be a universal Turing machine, whose inputs are restricted to Turing machines accepting languages in P. Let L=L(U) the language accepted by U, hence the acceptation language restricted to P."

Assume that such a universal Turing Machine U (referred as TM from now on) exists.

P contains an infinite number of problems (1) .

Why? Imagine the TM A[y] , y belongs to IR, with alphabet {0,1}. A[y]y accepts iff the input x has length greater or equal to y. It needs only 1 scan, therefore A[y] belongs to P. Since y is arbitary, it may take any value in IR. Therefore, there's an uncountable infinite number of problems in P. (y as decimal does not make much sense in the real world, still, this is a valid problem definition)

Therefore, the universal machine must depend on some property of the TM's that recognize language in P. Their only common property is that they require polynomial time to produce a result. (2)

(2) can be proven via diagonization. For any set of problems given, it is possible to construct one that has at least 1 foreign property with every other problem.

However, the "running time property" this is a non-trivial property, therefore by the Rice Theorem, such a TM can verify but not recognize the language (it may run infinitely). NP contains only definite TM's (they return YES or NO). Therefore , L is not in NP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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