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

71–80 of 87 posts

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

#71

Post by lisper »

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…

This result is slightly less interesting that it sounds. "an oracle X chosen uniformly at random from all oracles" is also called a "random oracle", more commonly referred to nowadays as a cryptographically secure pseudo-random number generator. So what this is really saying is that "an oracle X chosen uniformly at random from all oracles" is almost certain to not do anything more interesting than produce numbers that indistinguishable from random, and hence cannot be compressed. So yes, it's a cool result, but not quite as earth-shattering as it may appear to be at first glance.

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

#72

Post by Lerc »

This bit makes me wonder

> My longest-surviving proof that NP does not equal co-NP (about 5 years ago) survived for about 3 days and fooled some very smart people into believing it.

Is this a path towards selecting by insidiousness of mistakes? Can we mistakenly prove something by evolving a method by which no-one can figure out what is wrong with it.

Is there a limit to how hard it is to identify a mistake in a false proof? If incompleteness keeps you up at night, how about the possibility of a proof that you can have a mistaken proof in which the mistake was provably unidentifiable.

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

#73

Post by imakecomments »

sjclemmy wrote: post #61
stratfordfellow wrote: post #34

Earlier quoted context omitted.

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

I bought Sipser for this very purpose. I found it very difficult without being able to discuss it with anyone to clarify my understanding of the ideas. I would love to work through it, but would need a CS tutor to help me... any takers? ;) Edit: to be honest it's the maths notation that is a big barrier for me. Until one can read it relatively fluently it's very hard to translate the ideas into a meaningful mental mo…

It's been mentioned elsewhere but I recommend: https://www.youtube.com/playlist?list=PL601FC994BDD963E4

Seems like a few lectures are missing but if you google around you might be able to find them somewhere.

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

#74

Post by gone35 »

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…

Sure, but then again ex falso quodlibet... Just ask the academic cryptography community[1].

[1] https://arxiv.org/abs/cs/0010019

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

#75

Post by menssen »

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?

Gary Bernhardt's new Destroy All Software series on computation [1] is basically designed for this.

Not all that in-depth, but it's a great starting point.

[1]: https://www.destroyallsoftware.com/

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

#76

Post by kosievdmerwe »

SilasX wrote: post #67
tromp wrote: post #66

Earlier quoted context omitted.

Flip a coin for each string to decide its membership in the language. In other words, let the characteristic sequence of the language be an infinite random binary string.

So, a language is a mapping from strings to 1/0? And an oracle is a language?

A language is a set of strings and an oracle for that language answers whether a certain string is in that language in O(1) time.

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

#77

Post by JadeNB »

wnoise wrote: post #29
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's tricky and the notation confuses things a bit. P and NP are not the machine, but the set of problems solvable by deterministic/non-deterministic Turing machines limited to a polynomial number of steps. P^X is set of problems solvable by a deterministic Turing machine with access to oracle X, which is fairly straight forward, but need have little to with P. Similarly, NP^X is the set of problems solvable by a non…

> Essentially it boils down to: Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).

Indeed, it was just the worry that something nasty like this could happen that made me weasel my initial definite assertion into the form of a question. Thank you for this informal explanation; it nicely complements openasocket's formal reference (https://news.ycombinator.com/item?id=12893077).

(Long-delayed post because "You are submitting too fast".)

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

#78

Post by JadeNB »

bo1024 wrote: post #41
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? 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 d…

Thanks to you and wnoise (https://news.ycombinator.com/item?id=12893051) for excellent informal explanations that nicely complement openasocket's (https://news.ycombinator.com/item?id=12893077) formal one. I love instances where intuition needs to be corrected by rigorous reasoning.

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

#79

Post by Jweb_Guru »

Lerc wrote: post #72

This bit makes me wonder > My longest-surviving proof that NP does not equal co-NP (about 5 years ago) survived for about 3 days and fooled some very smart people into believing it. Is this a path towards selecting by insidiousness of mistakes? Can we mistakenly prove something by evolving a method by which no-one can figure out what is wrong with it. Is there a limit to how hard it is to identify a mistake in a fals…

Generally speaking, if there's a step that isn't clearly logically justified in your proof, the proof is considered wrong. So in most "normal" proof systems, this wouldn't really be a valid technique (that is, the moment someone tried to formalize it they'd run into this roadblock, and if it wasn't trivial to surmount the original proof would be thrown out). That said, there are some sequent calculi where you can do a lot of work in each step, so it might be really hard to figure out whether the step was valid; but I believe cut elimination theorems in those calculi basically assert that you can turn any valid "large step" into a (possibly very long, but finite) sequence of "small steps".

From a sociological perspective, since most mathematicians don't use formal methods for most of their proofs, there can of course be proofs that may be right, but that nobody can understand well enough to verify. The ongoing famous example here is that of Shinichi Mochizuki: http://www.nature.com/news/the-biggest-mystery-in-mathematic....

Anyway, neither of these seem too relevant to P vs. NP.

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

#80

Post by Nomentatus »

Reference needed: Once upon a time Turing Machines were my thing. But that was decades ago. Now I think I have a result that's interesting, following up on graduate school work I did way back when... but... reading such things as the P=NP prize problem definition I see that at least some terminology in the field has changed, or at least, concepts have been added. (Such as "language", if I remember rightly.) Can someone point me to sources that will allow me to translate Turing oldspeak into Turing newspeak, and vice versa?
Post reply on HN