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

The P=?NP Poll (2002) [pdf]

cs.umd.edu

Post reply on HN
Print view View original

11–20 of 87 posts

Re: The P=?NP Poll (2002) [pdf]

#11

Post by anandkulkarni »

lotsoflumens wrote: post #6
justifier wrote: post #4

Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. I believe that the traditional proof techniques will not suffice. Something entirely novel will be required. My hunch is that the problem will be solved by a young res…

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the ga…

>> complete absence of progress in proving P != NP

We've ruled out a number of techniques and also have shown that any solution must fall into a category avoiding a number of conditions (natural proof, algebrization barrier). Note also Ryan Williams' result separating ACC0 and NEXP. All of that is progress as I see it.

It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.

Re: The P=?NP Poll (2002) [pdf]

#12

Post by Analemma_ »

nabla9 wrote: post #8

I like Scott Aaronsons approach: Using NP hardness asumption as a physical constraint and seeing what follows. https://arxiv.org/abs/quant-ph/0502072

I second this; check it out even if you're not the type to usually read scientific papers. This is a fun one that's not hard to understand.

Re: The P=?NP Poll (2002) [pdf]

#13

Post by lotsoflumens »

anandkulkarni wrote: post #11
lotsoflumens wrote: post #6

Earlier quoted context omitted.

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the ga…

>> complete absence of progress in proving P != NP We've ruled out a number of techniques and also have shown that any solution must fall into a category avoiding a number of conditions (natural proof, algebrization barrier). Note also Ryan Williams' result separating ACC0 and NEXP. All of that is progress as I see it. It's simply that construction of practical approximation algorithms or heuristics that work on larg…

>> It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.

I agree, but the search for better algorithms is also more principled. At some point, separating complexity classes looks like counting the number of angels on a pinhead. It's probably interesting in an abstract way for some people - but it's not my cup of tea, as they say.

Re: The P=?NP Poll (2002) [pdf]

#14

Post by adilparvez »

A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.

An oracle is a black box that can solve a particular decision problem in O(1).

The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT.

It gets really ingesting because there are particular oracle machines for which P^X == NP^X.

See https://en.m.wikipedia.org/wiki/Oracle_machine for references to papers.

Also see https://en.m.wikipedia.org/wiki/Almost_surely if you don't know what with probability 1 is.

Off topic (but related to almost surely), one of my favourite theorems is Pólya's recurrence theorem which says that a simple random walk on Z^d (lattice) is recurrent for d=1,2 and transient otherwise, so if you get lost on a 1 or 2 dimensional grid, just execute a simple random walk and you'll get back to the origin almost surely! IIRC the probability of recurrence is about 34% in 3d.

Re: The P=?NP Poll (2002) [pdf]

#15

Post by pdpi »

DavidSJ wrote: post #9
pdpi wrote: post #5

Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us. http://www.informit.com/articles/article.aspx?p=2213858

It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...

With the caveat that it can never return false, which means it's not a complete solution.

Re: The P=?NP Poll (2002) [pdf]

#16

Post by VodkaHaze »

Is there any probabilistic argument around the proof?

For instance, a decade before Wiles' proof of Fermat's Last Theorem, Feynman[1] showed it was extremely unlikely to be false. While you're not getting a million from Clay for that, it something non insignificant that we can use to guide our intuition.

[1]http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem

Re: The P=?NP Poll (2002) [pdf]

#17

Post by Klockan »

DavidSJ wrote: post #9
pdpi wrote: post #5

Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us. http://www.informit.com/articles/article.aspx?p=2213858

It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...

This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.

Re: The P=?NP Poll (2002) [pdf]

#18

Post by JadeNB »

Klockan wrote: post #17
DavidSJ wrote: post #9

Earlier quoted context omitted.

It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...

This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.

> This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.

That seems to be an argument for the uselessness of the distinction between P-with-large-exponent and not-P, not for the uselessness of having a reduction of NP to P.

Also, it's worth noting that, if one is a theoretical computer scientist, then there is more of interest in the study of computing than what can be done in the universe. (I am a mathematician, and am, as I suspect most of my colleagues, serenely unconcerned with the applicability or non- of my work.)

Re: The P=?NP Poll (2002) [pdf]

#19

Post by lotsoflumens »

Jweb_Guru wrote: post #10
lotsoflumens wrote: post #6

Earlier quoted context omitted.

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the ga…

Sure, in some cases (the easy ones) we can solve NP-complete problems. However, tons of useful instances of NP-complete problems are not particularly close to being solved. We can even characterize fairly well when the instances become hard (for instance, for graph problems the treewidth seems relevant). I see absolutely no evidence that we're anywhere close to constructing a polynomial-time algorithm for any NP-comp…

>> (thus far, the biggest obstacle to proving P != NP has been the difficulty of proving anything about lower bounds on runtime that isn't directly tied to space consumption)

I probably don't understand the proofs of these bounds - it seems to me though, that any lower bound without some relationship to the time or space to input the problem into some kind of computer, implies a belief that an instance might be solvable in-place, in some physical system.

I have some doubts about that ....

Re: The P=?NP Poll (2002) [pdf]

#20

Post by JadeNB »

adilparvez wrote: post #14

A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…

> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.

Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)

Post reply on HN