El hecho de que existan oráculos $A,B$ tal que $P^A = NP^A$ , $P^B \neq NP^B$ (un teorema de Baker, Gill y Solovay) implica que el $P=NP$ La pregunta no puede resolverse con métodos "estándar" (porque se relativizaría a cualquier oráculo).
Edición: La mayoría de los métodos utilizados para demostrar las desigualdades de las clases de complejidad (por ejemplo, la diagonalización en la demostración de los teoremas de jerarquía espacial y temporal) funcionan incluso si se cambia el modelo de computación para permitir que un bit de computación sea "libre" (es decir, si la máquina de Turing puede acceder a un oráculo). El hecho de que tales métodos de "relativización" estándar no puedan bastar (según este teorema) para demostrar $P=NP$ o su negación se toma como prueba de que $P=NP$ es una cuestión seria y no trivial. Lo mismo ocurre con $NP$ frente a $coNP$ . Por cierto, es cierto que $P^A \neq NP^A$ en relación con un oráculo aleatorio (donde "oráculo aleatorio" significa que la pertenencia de cualquier cadena a $A$ se decide al azar) con probabilidad 1,* aunque esto no significa que $P \neq NP$ .
Un ejemplo de método no relativizador es la aritmetización de la fórmula booleana (que convierte una fórmula booleana en un polinomio que es distinto de cero en una asignación de las variables a ceros y unos si la fórmula es satisfacible con esos como las entradas correspondientes), utilizado en la demostración del teorema de Shamir que $IP=PSPACE$ , hecho que no es cierto en relación con los oráculos arbitrarios.
*La probabilidad tiene que ser cero o uno por la ley cero-uno de Kolmogorov, por cierto.
Hay una discusión muy interesante sobre el teorema Baker-Gill-Solovay en el blog de Terence Tao, aquí .
