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

[lisper]

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.

[komali2]

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

[stratfordfellow]

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

[groovy2shoes]

The Sipser book is excellent. It's one of only a handful of textbooks I decided to keep after I graduated from university. And perhaps the only one I kept because of how good it was rather than because the campus bookstore wanted to give me a pittance for it... and I didn't even buy the book until after the semester when I had to return the copy I'd checked out from the library...

I later on picked up the first two editions of Hopcroft & Ullman for $1 each at a used book store. I don't think either edition can really hold a candle to the Sipser book, which is shorter, more thorough, and (imo) easier to understand.

One caveat: it's super-expensive. I'd recommend finding a used copy or even an "international edition" (which will be soft-cover rather than hard-cover, but the content is the same).

[sjclemmy]

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

[imakecomments]

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.

[deckar01]

"Meta Math!: The Quest for Omega" by Gregory Chaitin [0] was my introduction to the theory of computability [1]. I found it enjoyable and approachable.

[0] https://books.google.com/books?id=Z6FJbwggW1sC

[1] https://en.m.wikipedia.org/wiki/Computability_theory

[austinl]

This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science).

Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?"

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

[mettamage]

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

The rest of computational theory will follow.

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

[menssen]

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/

[deathgrindfreak]

I'd start with an algorithms course, then progress deeper into Complexity theory. Perhaps a bit of discrete mathematics depending on your background.

[wildmusings]

Theory of Computation

[SilasX]

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?

[nialv7]

You can choose a random oracle by choose a language by random. Here a language means a set of strings.

[SilasX]

Can you explain that further? A random oracle is a random set of strings...?

[tromp]

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.

[SilasX]

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

[kosievdmerwe]

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.

[adilparvez]

Yes, I think it is like that.

[SilasX]

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

[nialv7]

This is not true. You can have oracles for uncomputable problems, like oracle for the halting problem.

[JadeNB]

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

[bo1024]

> 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]

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.

[wnoise]

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-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]

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

[openasocket]

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.

[JadeNB]

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

[adilparvez]

> 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]

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

[adilparvez]

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

[gone35]

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

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

[3pt14159]

What's the probability of recurrence in 4d or 5d? How does one calculate it?