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

91–100 of 303 posts

Re: A Solution of the P versus NP Problem?

#91

Post by zeptomu »

bmh_ca wrote: post #11
NikolaeVarius wrote: post #5

Earlier quoted context omitted.

>> This implies P not equal NP.

> This implies P not equal NP I did some graduate level research on P =? NP, specifically in the SAT space " rel="nofollow">https://en.wikipedia.org/wiki/Satisfiability> . In particular, I helped design MARMOSET (Marmoset Automated Reasoner Mostly Only Solves Easy Theorems), a competitive SAT problem solver. " rel="nofollow">http://www.cs.unb.ca/research-groups/argroup/marmoset/> . (It's a cool name... I didn't come…

> In particular, I helped design MARMOSET (Marmoset Automated Reasoner Mostly Only Solves Easy Theorems), a competitive SAT problem solver. [...]

Now that is some good SAT solver name - keeping user's expectations low, I guess? Nice choice! ;)

Re: A Solution of the P versus NP Problem?

#92

Post by hnaccy »

Govindae wrote: post #44
nerdponx wrote: post #31

Earlier quoted context omitted.

Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.

Well... The traveling salesman decision problem, not the general case. The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum. What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.

If you can solve the decision TSP in polytime you can solve the optimization case in polytime.

Re: A Solution of the P versus NP Problem?

#93

Post by Chinjut »

vanjoe wrote: post #64
DonbunEf7 wrote: post #62

Earlier quoted context omitted.

On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.

I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?

An algorithm could certainly be correct (in the sense of always giving the correct result) without being proven to do so (or even without any such proof existing, in some particular formal system). You are not wrong about that.

Re: A Solution of the P versus NP Problem?

#95

Post by sethrin »

vanjoe wrote: post #64
DonbunEf7 wrote: post #62

Earlier quoted context omitted.

On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.

I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?

Pretty much everything programmers do is create unproven algorithms. Hopefully at least some of them are correct. A heuristic is a problem-solving approach that has a chance of failure. So say you need a pretty fast dictionary, and you can take a relaxed attitude to correctness. You can take a hash of the words of your dictionary, and then as you are filtering some dataset, you can always say in a short time whether a value is definitely not in your dictionary, but your positive solutions have a percent chance of being incorrect (e.g. a hash collision). The idea is generally to make a problem tractable that would otherwise be computationally difficult or impossible. I'm not sure if that quite answers your question.

Re: A Solution of the P versus NP Problem?

#96

Post by zolthrowaway »

vanjoe wrote: post #56
zolthrowaway wrote: post #21

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.

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 algorithm that can crack it in polynomial time, regardless of whether the algorithm is known or not.

Re: A Solution of the P versus NP Problem?

#97

Post by baddox »

OJFord wrote: post #46
bradleyjg wrote: post #32

Earlier quoted context omitted.

Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)? Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.

It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order. If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?

Why would that be more surprising than the fact that some "natural" problems are polynomial and some are exponential, given that an exponential running time is asymptotically slower than any polynomial running time?

Re: A Solution of the P versus NP Problem?

#98

Post by MBlume »

mcguire wrote: post #78
Tomte wrote: post #39

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

" Yet here’s the bloodied patient, and here we are in the emergency room. " " The lemma encrusted shoulders of giants. " Aaronson on writes very well.

"At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you."

Re: A Solution of the P versus NP Problem?

#99

Post by MBlume »

vanjoe wrote: post #56
zolthrowaway wrote: post #21

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.

Alternately, a polynomial time algorithm is specified and the exponent is, say, 2500. Mathematically huge, practically useless.

Re: A Solution of the P versus NP Problem?

#100

Post by mmarx »

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.

Post reply on HN