Why We Still Can’t Solve P vs NP

The primary technical contribution of the paper is the demonstration that the P vs NP question has different answers in different relativized worlds. The researchers proved the existence of an oracle $A$ such that $P^A = NP^A$, indicating a collapse of the complexity hierarchy, and an oracle $B$ such that $P^B \neq NP^B$, indicating a separation. This duality proved that the internal logic of formal complexity models is consistent with both a collapse and a separation of the classes. It demonstrated that the fundamental difficulty of the problem is not a simple logical contradiction but is instead a result of the model's independence from the most common techniques used in mathematical logic.

The identification of this conflict established a rigorous bound on the power of diagonalization, a technique historically used to resolve the Halting Problem and Cantor’s uncountability proofs. Because diagonalization arguments typically relativize - meaning their conclusions remain true regardless of the presence of an oracle - Baker, Gill, and Solovay proved that no such argument could ever distinguish between P and NP. This insight forced a realignment in the field of complexity theory, shifting the focus from structural logic to the search for non-relativizing properties of circuits and algorithms. It effectively rendered the primary tool of 20th-century logic insufficient for the most significant problem in computer science.

The methodological choice to study machines with oracles revealed that the P vs NP question is fundamentally different from previous challenges in set theory and recursive function theory. The researchers demonstrated that the properties of "real-world" computation - where machines operate on raw strings without external aids - are not captured by arguments that remain robust across all possible information sources. This finding established that computational complexity is governed by specific, localized constraints that disappear when the model is extended. This realization remains the central theme for researchers seeking to bypass the structural barriers that have prevented a definitive proof for over half a century.

The success of this work provided the formal justification for the existence of "barriers" in mathematics, where specific classes of problems are proven to be immune to specific classes of proofs. By demonstrating that the relationship between P and NP is sensitive to the computational environment, the paper established a benchmark for evaluating the potential success of any new proof candidate. This realization led to the subsequent identification of other barriers, such as natural proofs and algebraic relativization, suggesting that the path to resolving fundamental complexity questions requires the discovery of new, deeply structural insights into the nature of information processing.