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

11–20 of 63 posts

Re: Predicting When P=NP Is Resolved

#11

Post by ggggtez »

einpoklum wrote: post #8
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.

> will this help up us to invent such algorithms? In addition to the obvious polynomial reduction between NP problems - which is usually not very practical - it is quite possible that this will help. > I don't see how “When I was a child, I spake as a child, I understood as a child, I thought as a child: but when I became a man, I put away childish things. For now we see through a glass, darkly; but then face to face…

Don't respond to a question with a vague quote, if you want to talk about putting away childish things.

If anything, it implies you don't actually know the answer either.

Re: Predicting When P=NP Is Resolved

#12

Post by marcosdumay »

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?

Since an algorithm for running NP-complete problems in P-time would be enough to prove whether P=NP, wouldn't the impossibility to prove it just prove that P!=NP?

Re: Predicting When P=NP Is Resolved

#13

Post by danharaj »

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.

P=NP? is such a difficult problem that it is more likely than not that a proof either way will necessitate extremely powerful new tools in complexity theory. It's hard to say what the impact on algorithm design and analysis would be.

Re: Predicting When P=NP Is Resolved

#14

Post by marcosdumay »

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.

> will this help up us to invent such algorithms?

It depends on the details, but it's very likely that the proof carries hints about how to create such algorithm.

But even if it doesn't, it being possible means that there is more value in searching for it than people expect today, so more people will look.

Re: Predicting When P=NP Is Resolved

#15

Post by jacobkg »

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.

Re: Predicting When P=NP Is Resolved

#16

Post by someguy12342 »

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…

Great post. Here are a few things pointers if you want more information about your points:

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")

C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind of unnatural). Search up "time hierarchy theorem". This is probably one of the theorems you mention. However, you're right, as far as natural problems go, it appears to be extreme difficult to prove most natural problems takes at least linear time (https://mathoverflow.net/questions/4953/super-linear-time-co...). Note the log*... factor grows extremely slowly.

In fact, it is not known whether SAT requires more than linear time. Since SAT is NP-complete, we expect it to have no polynomial time algorithm... and yet here we are wondering whether it requires even more than linear time. If you are interested in this sort of thing, maybe look up fine-grained complexity. Also note that to solve P != NP, we will have to atleast shown P != PSPACE, since PSPACE contains NP. However, even this seemingly easier problem has had no progress and seems like it would require a huge breakthrough.

Re: Predicting When P=NP Is Resolved

#17

Post by joe_the_user »

someguy12342 wrote: post #16
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…

Great post. Here are a few things pointers if you want more information about your points: 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") C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind…

>>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.

Re: Predicting When P=NP Is Resolved

#18

Post by joe_the_user »

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.

Working programmers and even people concerned with producing useful algorithm probably shouldn't care about P=NP?. It seems very likely to be true and if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed. Further, P!=NP is a theory entirely about worst case scenarios. Many NP complete problems are actually quite solvable in the average case and the worst case can have little relation to the average case (SAT solvers that are quite fast on average exist now, for example).

For logicians and mathematicians, a proof of N=NP? would be an incredible accomplishment simply because it's a problem that at this point no one know where to start on and so by definition, the proof would be a piece of remarkable and surprising mathematics giving people much to think on.

Re: Predicting When P=NP Is Resolved

#19

Post by raverbashing »

someguy12342 wrote: post #16
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…

Great post. Here are a few things pointers if you want more information about your points: 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") C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind…

From this it seems that the question itself might have been hopelessly naive

Is there any evidence that P might be equal to NP? This seems different from other famous conjectures like Fermat's Last Theorem or Riemann's Theorem where what's hard is finding a counterexample that disproves the theory.

Re: Predicting When P=NP Is Resolved

#20

Post by someguy12342 »

joe_the_user wrote: post #17
someguy12342 wrote: post #16

Earlier quoted context omitted.

Great post. Here are a few things pointers if you want more information about your points: 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") C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind…

>>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 (Baker, Gill, Solovay) that there exists and oracle O1 where

P^O1 subset NP^O1

as well as an oracle O2 such that

P^O2 not subset NP^O2

Therefore, we know we a proof of P != NP must not relativize or else that would contradict the aforementioned result.

Post reply on HN