¿Es posible demostrar que una oración debe ser formalmente independiente basada en el hecho de que no es relativizante? En otras palabras, ¿hay ejemplos de oraciones en la teoría de la computabilidad / complejidad donde se pueda demostrar tanto a) que todas las pruebas que resuelven la cuestión de si dos clases son iguales o no deben relativizarse, yb) que no hay pruebas relativizantes que se puede usar en tal resolución?
Creo que sería más fácil obtener resultados que satisfagan la parte b. Otra forma de hacer esta pregunta es: ¿Alguna vez ha habido una oración en la teoría de la computabilidad o la complejidad en la que se pueda demostrar que la igualdad o la desigualdad deben establecerse mediante el uso de (y solo mediante el uso de) técnicas de relativización? Un ejemplo de esto sería interesante para mí.
Gracias; Una respuesta a cualquiera de las versiones de esta pregunta sería muy interesante para mí.
-Philip
fuente