Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



p vs. np
Posted:
May 11, 2013 3:11 PM


Hello all,
After a hiatus, I've returned to my attempts to prove P != NP. I've found a proof avenue that I think is very good, and I think this technique that I've found can be used successfully to resolve the problem. It's possible that there is a glitch or two in the proof, but I don't think the approach has any fatal flaws.
Please find below my notes on how to prove P != NP. I haven't included every detail, but tried to use a step by step approach so that a specific lemma can be pointed to if someone thinks there's an error. I can give more detail in response to requests for clarification.
If anyone can provide any thoughts on my proof, I'd greatly appreciate this. The proof should not be too hard to follow for anyone who has worked through an introductory level book on TCS.
Specifically, I'm looking for: comments, errors, fatal flaws, thoughts on clarity/presentation. I'm hoping to email someone in the field sometime soon (not sure who I'll go with yet), but for now I want to get initial thoughts from regular math/TCS enthusiasts like myself. Hopefully I'll be able to get the proof so clear and readable that anyone with the right amount of training will be able to understand it quickly.
Thanks!
Philip
Proof idea:
Because relativization shows that diagonalization doesn't work in certain cases, we can exploit this to prove P != NP. Take the question of whether or not diagonalization can separate NP and EXPTIME. Based on an oracle result, we can show that diagonalization *cannot* separate NP and EXPTIME; further, we can zero in on a specific "diagonalization language" that must not be in EXPTIME because of the oracle result. Ultimately, we can show that this language still does belong to coNEXP, and thus that EXP != coNEXP. By the padding argument, this yields that P != coNP, and thus that P != NP.
A SRJNP = selfrejecting NPlimited machines. B Lemma 1: For all oracles O, SRJNP^O is not in NP^O. C Lemma 2: For all oracles O, (SRJNP^O is in EXP^O and SRJNP^O is not in NP^O) > (NP^O != EXP^O). D Lemma 3: If SRJNP is in EXP, then for all oracles O, SRJNP^O is in EXP^O. // hard, but doable E Lemma 4: There exists an oracle H s.t. NP^H = EXP^H. // proved by Heller F Lemma 5: SRJNP is not in EXP. // not that hard G Lemma 6: SRJNP is in coNEXP. // like Time Hierarchy H Lemma 7: EXP != coNEXP. I Main Theorem: P != NP. // padding argument
**********A**********
Definition: SRJNP = the language comprising all descriptions of NP limited machines that reject their own descriptions.
**********B**********
Simple diagonalization.
**********C**********
Trivial.
**********D**********
SRJNP is in EXP > SRJNP^O is in EXP^O.

Abbreviated version: We describe an explicit algorithm that uses dovetailing to decide SRJNP in EXP if any algorithm does. Then, we add an oracle to it, and show that it still decides SRJNP^O in EXP^O.
(Technically, we shift the focus to self*accepting* NP (SANP), as opposed to SRJNP. But the proof idea is the same.)

Detailed version:
We describe L, which is a multitasking dovetailing algorithm that dovetails over all EXP algorithms M on L's input I, one step at a time. That is, each EXP machine M is passed a copy of L's input I, and M(I) is simulated one step at a time during the dovetailing pattern. The dovetailing pauses after the completion of each computation M(I), and, if M(I) accepts, the output T that is yielded is used as a certificate in a separate simulation.
This separate simulation involves treating the input I as a nondeterministic polylimited machine that will be simulated on its own description with the polylimiting enforced. This simulation becomes a *deterministic* polynomial time simulation when the certificate T is supplied, and can be performed in EXP. Note that the certificate is not necessarily a *valid* certificate, only a candidate; thus, the computation I(I) may still reject, especially if it doesn't finish within the polynomial bounds.
The objective of L is to determine if a simulation of an NP machine on itself accepts. L accepts SANP in EXP iff any machine does (proof omitted), and we can show (proof omitted) that if a machine accepts in EXP, then there exists a machine that *decides* the language in EXP, too. Further, because EXP is closed under complementation, we have that SRJNP (selfrejecting NP machines) is in EXP if L's running time is EXP.
Now, fix an arbitrary oracle O. We now describe L^O, a machine that is just like L, but with oracle access to O. L^O differs from L in that L is simulating across EXP^O machines (and it uses its oracle access to O to achieve this simulation in EXP^O), and in that the NP machines it simulates also have access to O (and L can use its oracle to prevent slowdown in simulating these NP^O machines, too).
We can show that if any algorithm accepts SANP^O in EXP^O, then L^O is such an algorithm (much as L functioned above). Further, we can show that if an algorithm accepts SANP^O in EXP^O, then there exists an algorithm that decides SRJNP^O in EXP^O, since EXP^O is closed under complementation regardless of oracle (just switch the accept and reject states in the Turing machine).
Finally, when considering L and L^O, we can see that because adding an oracle to L enables L^O to handle SANP^O in the same amount of time as it was able to handle SANP without the oracle, L accepts SANP in EXP <> L^O accepts SANP^O in EXP^O.
These arguments together give us the following:
> L accepts SANP in EXP <> there exists an algorithm that accepts SANP in EXP > There exists an algorithm that accepts SANP in EXP <> there exists a machine that decides SANP in EXP > L runs in EXP <> SRJNP is in EXP (follows from the above) [For arbitrary oracle O.] > There exists an algorithm that accepts SANP^O in EXP^O <> L^O accepts SANP^O in EXP^O. > There exists an algorithm that accepts SANP^O in EXP^O <> there exists an algorithm that decides SRJNP^O in EXP^O. > L accepts SANP in EXP <> L^O accepts SANP^O in EXP^O.
From these conclusions, we can derive the fact that: SRJNP is in EXP > SRJNP^O is in EXP^O.
**********E**********
Proved by Hans Heller, see page 5 of his 1984 paper, "On Relativized Polynomial and Exponential Computations"
**********F**********
SRJNP is not in EXP
Let oracle O = H, Heller's oracle. From the contraposition of Lemma 3 and the fact that NP^H = EXP^H, we have that SRJNP^H is not in EXP^H or SRJNP^H is in NP^H. Because we know from Lemma 2 that SRJNP^H is not in NP^H, it's clear that SRJNP^H is not in EXP^H.
Now, by the contraposition of the dovetailing lemma, we have that for all oracles O, SRJNP^O is not in EXP^O > SRJNP is not in EXP. Letting O = H, we indeed have that SRJNP is not in EXP.
**********G**********
// Argument similar to the time hierarchy theorem.
**********H**********
SRJNP is in EXP but not coNEXP.
**********I**********
// Padding argument.



