Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: p vs. np
Replies: 0

 Philip White Posts: 3 Registered: 5/11/13
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 = self-rejecting NP-limited 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 (self-rejecting 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 slow-down 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**********