esearchers have used this knowledge to get a better grasp on the P versus NP problem. The first attempts at determining the relationship between P and NP used an elegant trick called diagonalization that had been essential for other major results in computer science. But researchers soon realized(opens a new tab) that any proof based on diagonalization would also apply to any world where every computer can consult the same oracle. This spelled doom, as oracles change the answer to the P versus NP question. If researchers could use diagonalization to prove that P and NP are different in the real world, the same proof would imply that P and NP are different in an oracle-infused world where they’re clearly equivalent. That means any diagonalization-based solution to the P versus NP problem would be self-contradictory. Researchers concluded that they’d need new techniques to make progress.
You are viewing a single comment's thread from: