Proof of P ≠ NP (2nd attempt)

https://news.ycombinator.com/item?id=41315042

by shunyaekam • 2 years ago

10 5 2 years ago

news.ycombinator.com

URL: https://shunyaekam.com/assets/papers/pvsnp.pdf

Second attempt. Apologies for the 1st attempt, didn't check the definitions properly.

Looking forward to useful criticism.

pookybear223• 2 years ago

Congrats sir!! What comes next? Do you view this as the end of this line of research or just the start of something new?? What consequences are there from this?? Hacker news is fantastic in that we get to rub shoulders with the greats like here and tptacek. -Armond

desertrider12• 2 years ago

L_R is not decidable. Deciding if x##y is in L requires simulating y until it produces |x| digits of output. x being anything and y = “while(true) {}” is a counterexample. Another way to look at it is that for any fixed x, "y produces x as its first |x| digits of output" is a nontrivial semantic property of y, so Rice's theorem shows that the property is undecidable.

shunyaekam• 2 years ago

R is basicially a function from rationals to algorithms computing irrationals.

L_R is decidable by a master algorithm running every y of x#y, e.g. 3.14#<y_pi> runs y_pi(|3.14|), so y runs up to 2 decimals.

The master algorithm runs y(|x|) and then compares the output to x.

It halts correctly for every x#y unless you can provide a counter-example?

kingkongjaffa• 2 years ago

Pls stop posting this here.

post the paper on https://arxiv.org/ or speak with your local university mathematics department. These would be far more qualified to assess a proof than HN.

I only ask because people who do mathematics in isolation are often quite naive and people reacting to such a fantastical proof on social media like here, are not equipped to evaluate it on its merits, (I’m certainly not, and unless you’re an active researching mathematician you’re probably not either)

devit• 2 years ago

Very unlikely that a half page proof of P!=NP is correct.

Please provide a formalization of your argument in any widely-used theorem prover (I'd recommend Lean) configured with options widely accepted to be sound.

BTW, the argument seems trivially bullshit because you say that L is in NP, and then claim that L is not P because "there exists no algorithm that...", but if L is in NP there is of course an exponential-time algorithm for L.

Proof of P ≠ NP (2nd attempt)

Related Stories