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

31–40 of 87 posts

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

#31

Post by openasocket »

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

It would seem not! I found a copy of the paper: http://www.cs.cornell.edu/courses/cs682/2006sp/handouts/benn... and it doesn't seem to specify any conditions. Apparently prior work has constructed specific oracles X such that P^X != NP^X. I think the paper is "Relativization of the P =?NP question" but I couldn't find a copy. Though I did find this http://www.cs.umd.edu/~jkatz/complexity/f05/relativization.p... which might help.

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

#32

Post by Jweb_Guru »

lotsoflumens wrote: post #19
Jweb_Guru wrote: post #10

Earlier quoted context omitted.

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 solva…

To be clearer, a trivial lower bound is something like "the input is of size n and for any n-1 length yes-instance you can find n-length extensions that are no-instances, so you have to check all n elements." It doesn't tell us anything interesting about the worst-case problem complexity. What's been surprising is how hard it is to make meaningful lower-bound statements stronger than that (well, not surprising to people who work on this stuff for a living, I guess). But that doesn't make it more likely that P = NP, really, except in the sense that we (obviously) haven't characterized the entire space of problems in P yet.

To more specifically address your "in-place" concerns, you can often formulate the problem in terms of circuit complexity--circuits are inherently parallel, so minimum circuit depth is a good proxy for a required number of steps, and it's also generally agreed that if you can design a circuit to do something it's physically realizable (even though that's arguably not always true, especially in cases with very wide fanout). So a (somewhat) promising direction has been to try to find circuit complexity lower bounds for problems, especially nontrivial ones.

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

#33

Post by [deleted] »

komali2 wrote: post #27
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…

Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?

[deleted]

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

#34

Post by stratfordfellow »

komali2 wrote: post #27
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…

Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?

What you're looking at is the theory of computational complexity.

Here's a short-ish overview: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/...

For a more extensive overview, try this textbook by Michael Sipser (Amazon Affiliate Link if feeling generous: http://amzn.to/2fy9tKZ, Google Books link otherwise: https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introducti...).

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

#35

Post by mettamage »

komali2 wrote: post #27
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…

Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?

Part 1 of 9 by Shai Simonson -- Finite State Machines

The rest of computational theory will follow.

https://www.youtube.com/watch?v=HyUK5RAJg1c

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

#36

Post by joaorico »

#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 scientists to produce a proof), we have a contradiction."

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

#37

Post by SilasX »

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?

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

#38

Post by woliveirajr »

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

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

#39

Post by JadeNB »

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…

> 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 able to deduce that P \ne NP; but we famously can't.

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

#40

Post by JadeNB »

openasocket wrote: post #31
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.)

It would seem not! I found a copy of the paper: http://www.cs.cornell.edu/courses/cs682/2006sp/handouts/benn... and it doesn't seem to specify any conditions. Apparently prior work has constructed specific oracles X such that P^X != NP^X. I think the paper is "Relativization of the P =?NP question" but I couldn't find a copy. Though I did find this http://www.cs.umd.edu/~jkatz/complexity/f05/relativization.p... which…

Thanks for that reference! I am glad that, even if my intuition led me astray, at least I had the foresight to append the weasel "… right?" to the end of my false claim. :-)
Post reply on HN