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.

- 447 reads