You are here

P vs. NP and Oracles

16 March, 2015 - 11:47
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

A well-known problem in computer science "P vs. NP" asks whether (for a given problem) it is truly more difficult to find a short solution (when one exists) ("NP"), than it is to verify a short purported solution handed to you ("P"). For example, "Given a set of people and how strong person is, can you partition them into two tug-of-war teams which are exactly evenly matched?" Certainly it seems easier to check that a pair of proposed rosters has equal strength (and, verify that everybody really is on one team or the other) than to have to come up with two perfectly-matched teams. But conceivably, the two tasks might be equally-difficult up to some acceptable (polynomial time) overhead. While every assumes that P is easier than NP, nobody has been able to prove it.

An interesting variant of the problem lets both the problem-solver and the purported-answer-verifier each have access to a particular oracle a prog ram that will gives instant yes/no answers to some other problem (say, "given any set of numbers, yes or no: is there an even-sized subset whose total is exactly the same as some odd sized subset?").

It has been shown that there is some oracle which makes the problem-solver's job provably tougher than the proof-verifier’s job, and also there is some other oracle problem-solver's job provably no-tougher than the proof-verifier’s job.

This means that any proof of P being different from NP has to be subtle enough so that when P and NP are re-interpreted as "P and NP with respect to a particular oracle", the proof will no longer go through. Unfortunately, this eliminates all the routine methods of proof; we know that solving this problem will take some new attack.