Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Solution of the P versus NP Problem?

arxiv.org

Post reply on HN
Print view View original

141–150 of 303 posts

Re: A Solution of the P versus NP Problem?

#141

Post by __s »

cvoss wrote: post #49
teton_ferb wrote: post #33

Earlier quoted context omitted.

Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve ? (P)". Note that the reverse is obviously true : problems that are easy to solve are also easy to verify . Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the…

(You may have omitted this detail on purpose, but I think it's worth pointing out) The example of trial division as a primality test is a good illustration of an algorithm that takes a lot of work to run but whose output is easy to verify. However, the problem of primality testing is actually in P. [1] You have to use a fancier algorithm than trial division in order to get polynomial time. [1] https://en.wikipedia.or…

This is a good example of Knuth's argument that some P=NP proof by non construction or massive polynomial could play out

https://cs.stackexchange.com/questions/23260/when-is-the-aks...

Re: A Solution of the P versus NP Problem?

#142

Post by kybernetikos »

monochromatic wrote: post #136
Analemma_ wrote: post #85

Earlier quoted context omitted.

Are you one of those people who equates any mention whatsoever of Trump as "being needlessly political"?

Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.

When you feel strongly about something and write about it, you aren't virtue signalling, you're expressing your view. If you have any reason to take the rather uncharitable stance that his views on Trump are inauthentic, then post them, otherwise it's better just to assume that people who say things you disagree with actually think those things rather than are just saying them to look good.

Accusing others of "virtue signaling" is a much clearer example of "virtue signaling" in my opinion, since it's a particular population that tends to do it, and is used primarily to put down those they disagree with and mark them as belonging to a different group rather than to actually make any kind of meaningful point.

Re: A Solution of the P versus NP Problem?

#143

Post by philipkglass »

phkahler wrote: post #80
DonbunEf7 wrote: post #63

Earlier quoted context omitted.

To follow up on this, in computational linguistics, there is a sharp divide between facts which take cubic time, like recognizing whether a string belongs to a context-free language, and facts which are halting-problem-hard, like recognizing whether two context-free grammars describe the same language. There doesn't appear to be much of a middle ground. In another realm of computational mathematics, matrix mjultiplic…

The AKS algorithm has been reduced to an exponent of 6. That really strikes me as large for polynomial time algorithms though.

The coupled cluster method CCSD(T), considered the "gold standard" of quantum chemistry, is O(N^7). That's the highest-exponent polynomial time algorithm I'm personally aware of that sees regular use. The various coupled-cluster variants are all basically approximations to full configuration interaction, which is a much worse O(N!).

Re: A Solution of the P versus NP Problem?

#144

Post by dom0 »

contradictioned wrote: post #120
teton_ferb wrote: post #33

Earlier quoted context omitted.

Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve ? (P)". Note that the reverse is obviously true : problems that are easy to solve are also easy to verify . Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the…

I want to add another important aspect, the aspect of NP completeness. There is a bunch of problems considered "NP complete" and they are all related such that it is easy to translate one problem into another (easy as in "quickly"). This means, first: If P == NP, then all of these problems become easy, and second: if P == NP and we find an algorithm that solves only one of the NP complete problems quickly, then this…

NP completeness kinda works around the uncertainty of PxNP (with x ∈ {⊆, ⊊}), because it defines some sort of "weak subset" of NP comprised of "pretty sure these problems are not in P[, because no one yet thought of a polynomial reduction to a problem in P]". The last part in brackets is the catch here; if we could show that it is not possible, then P!=NP would immediately follow, and NP completeness would become a largely pointless exercise.

Re: A Solution of the P versus NP Problem?

#145

Post by [deleted] »

jl6 wrote: post #101
lisper wrote: post #52

Earlier quoted context omitted.

FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

[deleted]

Re: A Solution of the P versus NP Problem?

#146

Post by 1ris »

__s wrote: post #138
1ris wrote: post #124

Earlier quoted context omitted.

Proof for the Gaussian correlation inequality was - Written in Word - Uses techniques just seem too wimpy for the problem at hand. - Was published in a predatory journal

Hence why Scott explicitly takes time to address that there will surely be outliers on both ends

I just wanted to point out that's is not a theoretical possibility, but actual ground breaking work did look sketchy as hell.

The "The nice thing about math is that sooner or later the truth comes out" bothers me. The knowlege in Archimedes palimpsest was lost so long the eventually doesn't seem to be much comfort.

Re: A Solution of the P versus NP Problem?

#147

Post by GenerocUsername »

jl6 wrote: post #101
lisper wrote: post #52

Earlier quoted context omitted.

FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

If only we had a way to make finding the flaw as easy as verifying the flaw

Re: A Solution of the P versus NP Problem?

#148

Post by Filligree »

GenerocUsername wrote: post #147
jl6 wrote: post #101

Earlier quoted context omitted.

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

If only we had a way to make finding the flaw as easy as verifying the flaw

I don't think it would be possible to make finding it as easy as verifying it, but how can we prove that?

Re: A Solution of the P versus NP Problem?

#149

Post by jjgreen »

jordigh wrote: post #70
jjgreen wrote: post #2

I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.

> serious cahunas I think you mean "cojones" (which btw is a very rude word in Spanish). A kahuna is a kind of Hawai'ian shaman.

I stand corrected, thank you. I would normally have said "serious bollocks", but this forum is mostly left-ponders who would probably not have caught my drift.

Re: A Solution of the P versus NP Problem?

#150

Post by StavrosK »

mmarx wrote: post #100
jjgreen wrote: post #2

I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.

> A career-ending disaster He is a tenured professor in Germany, there is very little that could end his career (essentially refusing to honour his teaching obligations or being convicted of a felony). At worst, this will be immensely embarrassing, but you can't kick professors out just because they make a fool of themselves.

And professors don't just make a fool of themselves because one of their papers had a flaw in it.
Post reply on HN