Cuando estaba explicando la prueba de Baker-Gill-Solovay de que existe un oráculo con el que podemos tener, , y un oráculo con el que podemos tener a un amigo, surgió una pregunta de por qué tales técnicas no son adecuadas para probar el problema , y no pude dar una respuesta satisfactoria.P ≠ N P...
¿Cómo demostrar que ? Solo estoy buscando un oracle TM M y un lenguaje recursivo L ( M ) = L para el cual esto es válido.N PUN≠ c o N PUNNPA≠coNPA\mathsf{NP}^A \neq \mathsf{coNP}^AMETROMML ( M) = LL(M)=LL(M) = L Sé que la prueba donde se demuestra que existe un oráculo tal que P A ≠ N P A y un...
Tomo curso sobre Complejidad Computacional. Mi problema es que no entiendo el método de relativización . Intenté encontrar un poco de intuición en muchos libros de texto, desafortunadamente, hasta ahora sin éxito. Apreciaré si alguien pudiera arrojar luz sobre este tema para poder continuar por mí...