Earlier quoted context omitted.
Sounds hard.
NP-hard. /dodge
That was the joke. :-)
A Solution of the P versus NP Problem?
241–250 of 303 posts
Re: A Solution of the P versus NP Problem?
#242I 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.
It's a common mistake - http://itre.cis.upenn.edu/~myl/languagelog/archives/003526.h... - and you could imagine a big kahuna would have to have serious cojones.
Re: A Solution of the P versus NP Problem?
#243Say you wanted to let a computer search for a proof of P!=NP - which axioms would you start with and which rules to transform the axioms into additional valid statements?
I wonder if the algorithm to search such a space of axioms and transforms for a solution would itself be P or NP. :)
Almost certainly so super-exponential that NP appears easy in comparison.
Re: A Solution of the P versus NP Problem?
#244So at least according to this P != NP. I’ve always been skeptical of this just because if you find an efficient optimal algorithm the problem moves between the classes.
>if you find an efficient optimal algorithm the problem moves between the classes This hasn't ever happened. You can prove an algorithm is in NP-hard by reducing another NP-hard problem to it. You can prove an algorithm is in P by showing the algorithm. If you find and efficient algorithm to a problem in NP-hard, you show P == NP. No one has ever done this. P != NP is considered by many to be most likely true.
> You can prove an algorithm is in P by showing the algorithm.
Thanks for clarifying - I always though that's what the above meant but I didn't realise that the reduction side was also important.
Re: A Solution of the P versus NP Problem?
#245Re: A Solution of the P versus NP Problem?
#246Earlier quoted context omitted.
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 l…
NP completeness would still be of interest for particular algorithms because it would prove that those problems could not be solved in polynomial time. For instance, if factoring was shown to be NP complete, that would be a really useful result both for showing the security of algorithms like RSA as well as potentially disproving the extended Church-Turing thesis if quantum computers can be created.
[deleted]
Re: A Solution of the P versus NP Problem?
#247Earlier quoted context omitted.
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.
This is absolutely correct. Proving P=NP doesn't magically create the algorithm, it just proves that there is one. However, the reason why I chose to single out crypto specifically is because it has the most to lose if that algorithm exists. Our current methods of encryption become unsafe regardless of whether the algorithm is known or not. I don't think you can claim that your encryption is secure if there is an alg…
> Proving P=NP doesn't magically create the algorithm, it just proves that there is one.
This is 100% true for all practical purposes. But there is an explicit algorithm for NP-complete problems that runs in polynomial time iff P=NP. The Wikipedia page has it written down. https://en.m.wikipedia.org/wiki/P_versus_NP_problem
Re: A Solution of the P versus NP Problem?
#248This is definitely one of those "I'm going to wait for the peer review" claims, but it is pretty exciting. Pros: The author is not a dilettante, and is actively researching in the area ( http://theory.cs.uni-bonn.de/blum/Forschung/forsch.var ) Cons: It's not my area, but I was expecting something a little more novel for a solution to P?NP. This almost seems too simple (it might almost fit in a margin...). Could be pr…
> However, Andrew Wiles... Grigori Perelman also comes to mind.
I would rather tell "Shinichi Mochizuki"
Re: A Solution of the P versus NP Problem?
#249I see a few typos in the wording of the paper (e.g., "spezify", "touchs", etc.). While this doesn't mean much, I would expect if the paper had gotten a fine-toothed comb review that these sorts of typos would have been caught. Moving back to the "not holding my breath" stance unless there start to be indications from experts in the field that the claims are holding up.
It's on ArXiv, people are free to publish there without getting a language review. The author's first language is not English.
Re: A Solution of the P versus NP Problem?
#250Earlier quoted context omitted.
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.
North American here, we hear enough Brits speak to get the expression :)
"serious bollocks" means "very questionable statement" in the British English I'm familiar with. Perhaps GP's idiom is from elsewhere. If the reference is to bravery/daring one would use "balls" as in US English, I believe.