71–80 of 303 posts
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 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.
It could easily cause some painful embarrassment, but hopefully that would pass with time.
Maybe embarrassment similar to that faced by researchers who's results suggested FTL communication, but it turned out to be a bad fiber-optic cable. I didn't follow up but I assume that team is doing OK.
Earlier quoted context omitted.
The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…
I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.
If someone could prove P=NP but no one could find an algorithm. That would be incredibly funny in some sense. Like a huge joke played on us by the universe.
Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?
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…
Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304
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."
- The proof will turn out to have a flaw
- The flaw will not be that hard to find (though probably not completely trivial; but rather of the kind: it takes much time to go to the details of the proof arguments)
- The flaw will not be interesting in itself and will not advance the field
If's its legit proof, they author should be able to explain why SAT2 is in P and SAT3 is NP-complete. That's my BS test.
Why? Proving something doesn't mean we understand all implications of said proof or how to apply it to a particular situation. Think about non-constructive proofs.
To me it does not seem that the author of the paper uses weird "coffeinated" non-constructive proof arguments in it.
Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304
Aaronson on writes very well.
Earlier quoted context omitted.
>Nobody's really interested in a proof that P != NP. I doubt that.
> Nobody's really interested in a proof that P != NP. This is not the case. In my day job I need to worry about what happens if ECDSA is broken. One way that can happen is quantum computation -- but that has a relatively transparent development timeline we can plan for. The other way in which ECDSA could be broken is if P==NP and the discrete log problem can be transformed in polynomial time into another polynomial t…
Earlier quoted context omitted.
This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. A…
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…