News for hackers. Stuff that matters.
Re:P ≠ NP by cdavidcash on Monday August 09, 2010 @01:01AM (#1587055)
Ah, that is not how those "barriers" work. Roughly, the relativization barrier goes like this: Say you have a proof that P!=NP. Does it also prove that P^A != NP^A for any oracle A? If it does, then the proof is flawed, because there <i>does</i> exist an oracle A such that P^A = NP^A!

Such proofs are said to relativize -- i.e., they are still valid relative to any oracle.

Re:P ≠ NP by long on Monday August 09, 2010 @11:01AM (#1588164)
Ah, thanks for explaining!