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

Predicting When P=NP Is Resolved

rjlipton.wordpress.com

Post reply on HN
Print view View original

41–50 of 63 posts

Re: Predicting When P=NP Is Resolved

#41

Post by intuitionist »

jacobkg wrote: post #15

In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in other words we may be in for a long wait. ^Perhaps because one of the hypothesized examples of a hard problem is the factoring of multiples of large primes (though not proved NP Complete). Or perhaps because they are both extremely famous open problems.

We know much less about P vs NP than we do about RH; we can prove weaker versions of RH (e.g. the prime number theorem) and analogues for other number systems (the Weil conjectures). This is unsurprising, since it hasn’t influenced math research for 160 years. Maybe someone will separate P and PSPACE before P and NP, or maybe they’ll fall at once to some brilliant new technique.

Re: Predicting When P=NP Is Resolved

#42

Post by skissane »

I have no idea what will be proven nor when. (My uneducated guess is not any time soon.)

But I hope it isn't "here's a proof that P!=NP". That'd be just too boring... Much cooler possibilities would be "here's a non-constructive proof that P=NP" or "here's a proof that P=NP is independent of ZFC".

Re: Predicting When P=NP Is Resolved

#43

Post by enriquto »

skissane wrote: post #42

I have no idea what will be proven nor when. (My uneducated guess is not any time soon.) But I hope it isn't "here's a proof that P!=NP". That'd be just too boring ... Much cooler possibilities would be "here's a non-constructive proof that P=NP" or "here's a proof that P=NP is independent of ZFC".

for me the most exciting would be "here's a constructive proof that P=NP. It uses polynomials of degree one million".

Re: Predicting When P=NP Is Resolved

#44

Post by lacker »

joe_the_user wrote: post #2

My pure amateur, possibly muddled understanding is that P=!NP is rather different from most open conjectures. A) It's extremely general or even "foundational" in the sense that it's asking whether any algorithm at all exists to solve an extremely general sort of problem in polynomial time. B) All of the standard methods used to solve problems of this sort have at least been pronounced exhausted at this point. C) Very…

It isn’t that different - most complexity theory conjectures are this way.

Basically, there are all these classes of algorithm. P can be solved in polynomial time, NP can be solved in polynomial time by a computer that gets really lucky with rng, PSPACE can be solved with polynomial space, L can be solved in logarithmic space. For many of these pairs, it kinda feels like they are not the same, but we can’t prove it.

So in particular we don’t know that P != PSPACE, which is a much weaker statement, and a very similar one, compared to P != NP.

Similarly, we can’t prove there are cryptographically secure hash functions, and we can’t prove it’s hard to factor numbers.

Basically, we just have very few mathematical tools for proving that complexity classes are different. It’s hard to prove that algorithmic problems are hard. We have diagonalization, which shows that the halting problem is impossible and that P != EXPTIME, and that’s about it.

Anyway, I would conclude not that P != NP is a uniquely hard problem, as much as that complexity theory is very young compared to most fields of mathematics, and there are still many statements we can’t prove.

Re: Predicting When P=NP Is Resolved

#45

Post by lacker »

AwesomeLemon wrote: post #3

Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.

It would be pretty handy for cryptography to have a better understanding of which problems were hard. P != NP we are already assuming, but if we could use the mechanism on other problems (like knowledge of exponent, discrete log, etc) it would help.

Re: Predicting When P=NP Is Resolved

#46

Post by chx »

enriquto wrote: post #43
skissane wrote: post #42

I have no idea what will be proven nor when. (My uneducated guess is not any time soon.) But I hope it isn't "here's a proof that P!=NP". That'd be just too boring ... Much cooler possibilities would be "here's a non-constructive proof that P=NP" or "here's a proof that P=NP is independent of ZFC".

for me the most exciting would be "here's a constructive proof that P=NP. It uses polynomials of degree one million".

While Knuth has a different take on the P=?NP problem than most others, namely he believes P=NP, nonetheless, he is also saying that the degree won't ever be known and not even an upper bound will be known for it. http://www.informit.com/articles/article.aspx?p=2213858&WT.m... Certainly "if P=NP it'll be a pure non-constructive proof with no practical consequence whatsoever" feels right.

Re: Predicting When P=NP Is Resolved

#47

Post by pwdisswordfish2 »

someguy12342 wrote: post #20
joe_the_user wrote: post #17

Earlier quoted context omitted.

>>B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization") I've heard of those, even tried to read the proof. Still, my understanding is those claims are ultimately "informal proofs" despite having formal step so the situation isn't entirely closed-up but still very bad.

Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A strict subset B they also show A^O strict subset B^O for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem) However, we know (B…

P^O is always a subset of NP^O, whatever the O.

Re: Predicting When P=NP Is Resolved

#48

Post by gield »

hinkley wrote: post #27
kibwen wrote: post #4

Is it possible to prove that a proof exists for either P=NP or P!=NP? Conversely, is it possible to prove that the conjecture is unprovable?

When people try to use 'NP complete' as a dodge for doing difficult coding at work, I point out to them that Claude Shannon proved that generalized compression algorithms can't exist, and yet we are surrounded all day by compression algorithms. Just because the space in NP hard doesn't mean that your problem is automatically NP hard. Lots of human consumable or generated data is full of patterns that can be exploited…

>[...] I point out to them that Claude Shannon proved that generalized compression algorithms can't exist [...]

What proof are you talking about?

Re: Predicting When P=NP Is Resolved

#49

Post by elfexec »

AwesomeLemon wrote: post #3

Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.

> Should we even care for a mathematical proof that P=NP?

Should we care about the most important computational problem in the world today? I'd say yes.

> Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.

Why does the method of proof matter? If it is proved that P=NP, then it means most of the pressing computational problems today are solvable in polynomial time. So we can double our efforts in trying to find these solutions. If it is proven that P!=NP, then we can stop wasting our time or just work on solving subsets of these problems. The problem is that we don't know whether the problems can be solved in polynomial time.

Put it this way. Which scenario would you prefer.

Scenario 1: There MAY be a billion dollars hidden somewhere in Mount Denali.

Scenario 2: There IS a billion dollars hidden somewhere in Mount Denali.

Scenario 3: There ISN'T a billion dollars hidden somewhere in Mount Denali.

Currently, we are at scenario 1. We don't know whether our efforts are for naught. We don't know if we haven't found the billion dollars because it's in a place we haven't looked or if the billion dollars isn't even in the mountain.

Proving P=NP, would get us to scenario 2. We know there is a billion dollars there, but we just have to find it. Proving N!=NP would get us to scenario 3. We know the billion dollars isn't there so we don't have to bother wasting our time.

I'd say we'd be in a much better position if we were in scenario 2 or 3 than the current scenario 1 we are at right now.

Re: Predicting When P=NP Is Resolved

#50

Post by joe_the_user »

pwdisswordfish2 wrote: post #47
someguy12342 wrote: post #20

Earlier quoted context omitted.

Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A strict subset B they also show A^O strict subset B^O for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem) However, we know (B…

P^O is always a subset of NP^O, whatever the O.

I think the gp left out the strict before the later subset statements.
Post reply on HN