2 ms·
> 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
by 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.