p vs. np

[Philip White]

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**********

// Padding argument.

[xlt...@gmail.com]

Here is the best, most succinct summary I think I can post. diagNP means "the main diagonal of NP." More details available upon request; step 3 is the only hard one to prove, and step 5 is the one that doesn't relativize.


Summary -

diagNP is not in NP relativizes.
diagNP is in NEXP relativizes.
diagNP is in EXP --> "diagNP is in EXP" relativizes.
diagNP is in EXP --> "NP != EXP" relativizes.
relative to an oracle for HELLER: NP = EXP.
NP != EXP does not relativize.
diagNP is not in EXP.
EXP != NEXP.
P != NP.

[xlt...@gmail.com]

Note: I should have said, "Either step 5 or step 6 doesn't relativize." It's actually very elegant to see how this works, but I'm leaving it as an exercise for the reader. Hint: Assume "NP != EXP does not relativize" does relativize (for the sake of contradiction).

Here's a proof of step 3:

An NP machine is a constant "certificate generator" or "guesser" G that generates all certificates, plus a polytime "checker" M that verifies the validity of the certificate; the upper bound on the running time of M individually is n^|M|+|M| for the input passed to M, and the certificate guesser guesses from the null string up to a unary string of all 1's of length n^|G+M|+|G+M| for the input given to the whole machine.

An algorithm multitasks over the guesser, one step at a time, and the checker, to check each appearance of a string on the guess tape to evaluate each guess. Fully processed and rejected guesses prompt the multitasker to return to the guess tape for the next step; an accepted guess prompts the entire machine to accept and halt.

The "guesser," being one fixed machine, does not need and does not have oracle access; the checker, which may be any polytime machine, has oracle access.

Assume diagNP is in EXP. Then, crucially, when deciding diagNP, we can replace the guesser with a single fixed FEXP machine that also does not query the oracle.

Add an oracle O. Crucially, the guesser hasn't changed, since it doesn't have oracle access; it's still just EXP. The polytime checker is being directly simulated, so observe that this P^O machine can still be simulated in EXP^O.

This yields that both the guesser (EXP) and checker (P^O) of the NP^O machine can be simulated in EXP^O. Thus, diagNP is in EXP implies for all oracles O, diagNP^O is in EXP^O, which is equivalent to "diagNP is in EXP" relativizes.

[xlt...@gmail.com]

Also, I should have said coNEXP instead of NEXP. And I'm not *positive* that step 2 relativizes. So:

diagNP is not in NP relativizes.

diagNP is in coNEXP.

diagNP is in EXP --> "diagNP is in EXP" relativizes.
diagNP is in EXP --> "NP != EXP" relativizes.
relative to an oracle for HELLER: NP = EXP.
NP != EXP does not relativize.
diagNP is not in EXP.

EXP != coNEXP.
P != NP.


...is the correct summary. Finally, I really shouldn't call it HELLER, because it was really Dekhtyar who first proposed the oracle relative to which NP^A = EXP^A. Oh well.

[My Father]

In other words just like a baseball diamond each square is first a right diagonal followed by three left diagonals before reachin home. Philip White, read my post I wrote aside the same night I wrote this reply about "there exists an algorithm" or variation to solidify the foundational elements of the proof. Whether it is your proof or mine is irrelevant, only whether it is proof is relevant.

[My Father]

[lite beta]

I saw this proof somewhere.

P=NP
if and only if
P-NP=0
if and only ife
P(1-N)=0
if and only if
P=0 or N=1

So if you want to prove P!=NP, it suffices to prove that both P!=0 AND N!=1

[Norbert_Paul]

Cool. But this then proves P!=PN. So it is only yet another reduction of
P!=NP to PN!=NP.

[m.michae...@gmail.com]

Hi Philip,

<Michael> Musatov here, remember me?! Here is my proof string. It works I think! 1
2
3 4
5 6
7 8
9 10 2 6 12 18 20 false
1 4 9 16 25 true

[m.michae...@gmail.com]

After On Saturday, September 21, 2013 12:57:15 PM UTC-5, m.michae...@gmail.com wrote:

I posted it as Keeson on this blog http://www.scottaaronson.com/blog/?p=1517#comment-87928

[federat...@netzero.com]

On Saturday, May 11, 2013 2:11:29 PM UTC-5, Philip White wrote:
> 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.

Yeah, this: you're making things more complicated than they need to be. If you're going to formalize diagonalization itself, then why not just formalize P and NP?

The formalizations are axiom systems. They can be subject to analysis within the framework of Boolean algebra.

There is a close link between the P = NP problem and the very process of automated analysis of axiomatizations. For instance, if you have a set S of statements and a set M of models, you can set up a disjunctive normally orderd term over the free lattice L(S) of S, where each row is the conjunction
A(m) AND {A(m,s): s in S}
where
A(m,s) = s, if m |= s; A(m,s) = not s else.
The clause, itself being
A = OR { A(m): m in M}.

Converting this into conjunctive normal form yields the set C of conjectures involving statements in S that are consistent with the models in M.

Now compare to the P = NP problem. The archetypical NP-complete problem is satisfiability. What this corresponds to -- when converting from conjunctive normal order (CNF) to disjunctive normal order (DNF) -- is whether a given CNF has a non-trivial DNF. In terms of models and statements, this corresponds to the question of whether a set C of conjectures has a non-empty set M of models.

Going in the reverse direction, the dual problem is universality. For a given DNF, the question is whether its CNF is non-trivial in the sense of being something other than a tautology; i.e. whether it's falsifiable. Here, the question is whether a set M of models yields a non-trivial set C of conjectures.

Sorry if I'm a little murky on that last point. I've only just started thinking about it.

But the point remains this: if you're going to axiomatize the things involved in P = NP, then you might as well axiomatize P and NP themselves and apply the kinds of analysis like those just described to the respective axiom systems. Denote the axioms for the respective classes S_P and S_{NP}. Then you're actually asking whether S_{NP} -> S_P is universal or not. In particular, you're taking
S = { S_{NP} -> s: s in S_P }
and asking whether this is universal.

[m.michae...@gmail.com]

On Friday, October 25, 2013 2:02:37 PM UTC-5, federat...@netzero.com wrote:
> On Saturday, May 11, 2013 2:11:29 PM UTC-5, Philip White wrote:
>
> > 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.

interview monday>
>
>
> Yeah, this: you're making things more complicated than they need to be. If assumption you stole 1b-value you're going to formalize diagonalization itself, and state you made it more complicated than they need 1b-value then why not just formalize P and NP?
I did (5P – 4P) = NP
(2, 2, 11, 1297) = 4P
(424,866,199,037,051) = P
NP=24,246,264,246,646,426,468 I knew there was a house 4 everything >

>
>
> The formalizations are axiom systems. They can be subject to analysis within the framework of Boolean algebra.
>
>
>

> There is a close link between the P = NP problem and the very process of and I have a little 5-year old I was born in Minnesota the lifestyle of living off of a seventeen-year old girl has kept me here year-round I wanted it automated analysis awesome of axiomatizations. Raise my daughter. Talitha cumi. For instance, if you have a set S of statements and a set M of models, you and mme you can set up a disjunctive normally ordered (erased evidence red by adding overlooked e value written as orderd term over the free lattice L(S) of S, where each row is the conjunction Lazar (Lazarus)
> I think I just give him an idea going for a blue need server code

> A(m) AND {A(m,s): s in S}
>
> where
>
> A(m,s) = s, if m |= s; A(m,s) = not s else.
>
> The clause, itself being
>
> A = OR { A(m): m in M}.
>
>
>
> Converting this into conjunctive normal form yields the set C of conjectures involving statements in S that are consistent with the models in M.
>
>
>

> Now compare to the P = NP problem. The High archetypical mystery NP-complete going home problem is satisfiability. What this corresponds to -- when converting from conjunctive normal order (CNF) to Go in my God come into Martin isjunctive normal order (DNF) -- is whether a given CNF has a non-trivial got one in love this open space her sister DNF. In terms of models and statements, this corresponds to the question of whether a set C of conjectures has a non-empty set M of models.

>
>
>
> Going in the reverse direction, the dual problem is universality. For a given DNF, the question is whether its CNF is non-trivial in the sense of being something other than a tautology; i.e. whether it's falsifiable. Here, the question is whether a set M of models yields a non-trivial set C of conjectures.
>
>
>

> Sorry if I'm a little murky on that last point. I've only just started trueificain thinking about it.

[Logic]

I've noted this:beat Bush. Either way, it's indisputable that he loses the election. > > > > KBA is saying: I, Philip, am losi
beat Bush. Either way, it's indisputable that he loses the election.
>
>
>
> KBA is saying: I, Philip, am losing to Snowden. Everyone likes Snowden; it sort of doesn't make sense, Philip knows what he's talking about and what he's doing. Why is Snowden the rockstar and Philip the abandoned one? One is named after a bear and the house of the cubs unintentionally is always going to get the care at first.

[Musatov]

On Saturday, May 11, 2013 12:11:29 PM UTC-7, Philip White wrote:

With no announcement predict one does n
With announcement predict one does P
Announce you will do n
P
n