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

21–30 of 63 posts

Re: Predicting When P=NP Is Resolved

#21

Post by jakear »

ggggtez wrote: post #11
einpoklum wrote: post #8

Earlier quoted context omitted.

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

The point of the quote is to say that they don't know the answer either. So, yes.

Think of it as: we are all children when it comes to the ramifications of the proof of P vs NP. We do not know the impact; we cannot know the impact. We will know it when it arrives.

Re: Predicting When P=NP Is Resolved

#22

Post by H8crilA »

marcosdumay wrote: post #12
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?

Not really, we don't know if human reasoning is contained in P, BPP, BQP, PP or even PSPACE (is there a ghost in this shell?). It may not be. Though human reasoning probably is contained in P, just like probably P != NP.

Re: Predicting When P=NP Is Resolved

#23

Post by someguy12342 »

raverbashing wrote: post #19
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…

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.

I think RJ Lipton (blog author) and Knuth believe it could be true. However, most complexity theorists don't (I think Fortnow does a survey of theorists on this every few years). Knuth says something like "well all it would take is a single algorithm for any of these hundreds of problems". A fine take for the godfather of algorithms. At the same time, there are many people who have in some sense tried to find such an algorithm, even non-explicitly (e.g. factoring would be in P if P = NP). Moreover, there is a lot of complexity theoretic work which makes it hard to believe it to be true (I think Scott Aaronson's blog has some presentable information about this)

Re: Predicting When P=NP Is Resolved

#24

Post by bloak »

marcosdumay wrote: post #12
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?

You could perhaps have a program that for every input you've tried gives the correct answer in polynomial time, but you haven't yet proved that it always will.

Nevertheless, I don't see how the answer to P!=NP could depend on the choice of axioms for set theory. Programs, their inputs and the state of a machine after executing n steps can all be encoded as integers, so P!=NP can be expressed as a statement about integers, and we know what the integers are: we don't need any dodgy set theory axioms for that.

If that's wrong, someone please explain how.

There are lots of interesting unsolved questions about integers (Goldbach's conjecture, ...) but people don't usually suggest that the answer to those questions might depend on the Axiom of Choice. Or do they?

Re: Predicting When P=NP Is Resolved

#25

Post by hinkley »

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.

One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint.

So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler on the surface and gave insights into a P solution, but either nobody has, or the right phrasing about it has caught nobody's attention.

There's an XKCD lamenting something pretty similar. You solved some unsolved problem but nobody will ever know because it's buried in a bug fix for your obscure little product.

Re: Predicting When P=NP Is Resolved

#26

Post by AnimalMuppet »

joe_the_user wrote: post #18
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…

P=NP is very likely to be true? I would say it's very likely to be false.

Why do I say that? Because it's possible to construct, say, SAT3 problems such that it seems impossible to solve them in polynomial time. If some problems can't be solved in polynomial time, then P!=NP.

Why do you think that it's "very likely" that P=NP?

Re: Predicting When P=NP Is Resolved

#27

Post by hinkley »

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 to useful purpose, even when purely random inputs are intractable.

Re: Predicting When P=NP Is Resolved

#28

Post by Laakeri »

joe_the_user wrote: post #18
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…

SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.

Re: Predicting When P=NP Is Resolved

#29

Post by ookdatnog »

marcosdumay wrote: post #12
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?

Surprisingly, a theorem being unprovable does not mean that the theorem is untrue, even if you can prove its unprovability! This was shown by Goedel (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...). He showed that there exists no system powerful enough to express theorems about the natural numbers which can prove all facts about natural numbers and be sound (ie not prove things that are untrue).

Re: Predicting When P=NP Is Resolved

#30

Post by lidHanteyk »

throwawaymath wrote: post #6
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?

Yes, and yes. P != NP could be independent from Peano Arithmetic (PA) or the Zermelo-Fraenkel set theory with Axiom of Choice (ZFC) models. That is a separate conjecture which is also presently open.

Surprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem.

> At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't!

[0] https://www.scottaaronson.com/papers/pnp.pdf

Post reply on HN