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

41–50 of 87 posts

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

#41

Post by bo1024 »

JadeNB wrote: post #20
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.)

> If P = NP, then P^X = NP^X for any oracle X, right?

No, surprisingly, it's not true!

The problem is that a nondeterministic turing machine can ask "more" or "better" questions of an oracle than a deterministic one. Intuitively, it can ask an exponential number of questions and then accept if any of the answers turn out to be "useful".

So even if we know they solve the same problems when unaided by an oracle, this doesn't imply that an oracle amplifies their abilities in the same way.

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

#42

Post by [deleted] »

adilparvez wrote: post #25
JadeNB wrote: post #20

Earlier quoted context omitted.

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

> If P = NP, then P^X = NP^X for any oracle X, right? Edit: No, I think. See child comment by JadeNB. Probably wrong { Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class). } I hope this is clearer, let {A, B, C, ...} be the set of all oracles. For TM + A: P^A is the class of prob…

[deleted]

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

#43

Post by bo1024 »

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…

It's true that there has been a lot of practical progress and even theoretical progress, though often of the form "we improve 1.8^n running time to 1.65^n". But...

> As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast.

I'd disagree. As we develop more and more understanding of these problems, we still are only improving exponentials to other exponentials (in theory - practice may be different) and so we remain in a fundamental sense as far away from polynomial-time solutions as ever, despite improved understanding.

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

#44

Post by adilparvez »

JadeNB wrote: post #39
adilparvez wrote: post #25

Earlier quoted context omitted.

> If P = NP, then P^X = NP^X for any oracle X, right? Edit: No, I think. See child comment by JadeNB. Probably wrong { Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class). } I hope this is clearer, let {A, B, C, ...} be the set of all oracles. For TM + A: P^A is the class of prob…

> Yes, since we could just not invoke the oracle. I think that only shows that P^X contains P and NP^X contains NP, not that P = NP implies P^X = NP^X. Indeed, my supposition that this implication holds seems to be false; openasocket ( https://news.ycombinator.com/item?id=12893077 ) points to a paper mentioning a specific example of an oracle B so that P^B \ne NP^B. If my naïve reasoning were correct, then we'd be ab…

Cool, I shouldn't make assumptions, thanks for the link.

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

#45

Post by adilparvez »

SilasX wrote: post #37
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…

What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each problem corresponds to an oracle for that problem?

Yes, I think it is like that.

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

#46

Post by SilasX »

adilparvez wrote: post #45
SilasX wrote: post #37

Earlier quoted context omitted.

What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each problem corresponds to an oracle for that problem?

Yes, I think it is like that.

Another way to enumerate oracles is to consider the set of terminating Turing machines (and enumerating them is itself uncomputable but whatever). Each TM corresponds to an oracle that computes its result in O(1).

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

#47

Post by OJFord »

woliveirajr wrote: post #38
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

I love his timing: Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic

   > by either 2048 or 4096
It's an odd statement for a mathematician/computer scientist. It's equivalent to "by 4096", surely.

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

#48

Post by VLM »

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

That is one interesting way to interpret the famous Aaronson soap bubble experimental results, and Yuri Gurevich's opinion is just a somewhat more optimistic version of it.

Because of some hand wavy string theory calculation completed in 2030, either the universe doesn't exist as it is measured to exist (or whatever McGuffin you'd like as a bullet proof excuse) or there exists a Turing machine that outputs a proof of P=NP then halts and the fastest way to find out if it halts is to run it and we try and it never stops. Maybe a century later someone figures out a lower bound on the number of steps the machine will make before it halts and its larger than the computational power of the lifetime of the universe, even very optimistically. Or a ruleset is proven to exist but the ruleset is at minimum a number larger than the number of particles in the universe so its kinda difficult to construct or emulate. Or the infinitely long Turing tape is merely proven to contain a number of states equal to a trillion times the number of atoms in the universe.

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

#49

Post by surrey-fringe »

joaorico wrote: post #36

#8 is a fun one (some of these answers are half-joking): "Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer…

Is that true -- that the proof (if we produce one) will be verifiable in polynomial time?

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

#50

Post by kamilner »

VodkaHaze wrote: post #16

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

As mentioned elsewhere in the thread, if provided with a random oracle A, P^A != NP^A with probability 1. It's not clear though what this actually buys you, intuition wise, since it's already sort of intuitively clear that nondeterministic oracle queries are much more powerful (then again, I guess you could say the same about nondeterministic computing...)

http://epubs.siam.org/doi/abs/10.1137/0210008

Edit: For those who are interested, the oracle separation gives you one of the few properties we can prove about the nature of any proof of P ?= NP, that it must be 'non-relativizing'. We know a few other properties of any possible proof, described here: http://www.scottaaronson.com/papers/alg.pdf

Post reply on HN