6 ms·
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
by adilparvez 10y ago
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 https://en.m.wikipedia.org/wiki/Oracle_machine for references to papers.
Also see https://en.m.wikipedia.org/wiki/Almost_surely 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.
- JadeNB 10y ago> 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.)
- adilparvez 10y ago> 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 problems that can be done in P time on this machine. NP^A is the class of problems that can be done in NP time on this machine. Similarly for TM + B TM + C ... This theorem says that if we choose one of these oracle machines uniformly at random then P =/= NP in _its_ model of computation a.s. This is an entirely probabilistic statement about machines that are more "powerful" than standard TMs.
- JadeNB 10y ago> 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 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.
- adilparvez 10y agoCool, I shouldn't make assumptions, thanks for the link.
- deleted 10y ago[deleted]
- wnoise 10y agoIt'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-deterministic Turing machine with access to oracle X. However, this means if there's any input it could ask X to get an answer it can use to solve the problem, it can solve the problem, which may be vastly more efficient than trying to construct the right question to ask. 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).
- JadeNB 10y ago> 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 https://news.ycombinator.com/item?id=12893077). (Long-delayed post because "You are submitting too fast".)
- openasocket 10y agoIt would seem not! I found a copy of the paper: http://www.cs.cornell.edu/courses/cs682/2006sp/handouts/bennettgill.pdf 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.pdf http://www.cs.umd.edu/~jkatz/complexity/f05/relativization.p... which might help.
- JadeNB 10y agoThanks 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. :-)
- bo1024 10y ago> 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.
- JadeNB 10y agoThanks to you and wnoise (https://news.ycombinator.com/item?id=12893051 https://news.ycombinator.com/item?id=12893051) for excellent informal explanations that nicely complement openasocket's (https://news.ycombinator.com/item?id=12893077 https://news.ycombinator.com/item?id=12893077) formal one. I love instances where intuition needs to be corrected by rigorous reasoning.
- komali2 10y agoAnyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?
- marcoperaza 10y agoTheory of Computation
- deleted 10y ago[deleted]
- stratfordfellow 10y agoWhat 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/Hogan.pdf 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 http://amzn.to/2fy9tKZ, Google Books link otherwise: https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introduction+to+theory+of+computation https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introducti...).
- sjclemmy 10y agoI 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 model .
- imakecomments 10y agoIt's been mentioned elsewhere but I recommend: https://www.youtube.com/playlist?list=PL601FC994BDD963E4 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.
- SilasX 10y agoWhat 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?
- adilparvez 10y agoYes, I think it is like that.
- SilasX 10y agoAnother 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).
- nialv7 10y agoThis is not true. You can have oracles for uncomputable problems, like oracle for the halting problem.
- nialv7 10y agoYou can choose a random oracle by choose a language by random. Here a language means a set of strings.
- 3pt14159 10y agoWhat's the probability of recurrence in 4d or 5d? How does one calculate it?
- lisper 10y agoThis 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.
- gone35 10y agoSure, but then again ex falso quodlibet... Just ask the academic cryptography community[1]. [1] https://arxiv.org/abs/cs/0010019 https://arxiv.org/abs/cs/0010019