Ejemplos de juguetes para barreras a

¿Hay ejemplos de juguetes que brinden información 'esencial' para comprender las tres barreras conocidas para el problema : relativización, pruebas naturales y algebrización?$P = NP$

Permítanme dar un ejemplo de juguete de la barrera de relativización. El ejemplo canónico es el teorema de la jerarquía temporal que . La prueba (por diagonalización) es solo un poco más complicada que la prueba de que el problema de detención es indecidible: definimos un algoritmo A ( x ) que simula el algoritmo x th A x en la entrada x directamente paso a paso para t ${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$$A(x)$$x$$A_x$$x$ pasos, luego genera el valor opuesto. Luego argumentamos que A puede implementarse para ejecutarse en t ( | x | ) 2 veces.$t(|x|)$$A$$t(|x|)^2$

El argumento funciona igualmente bien si equipamos a todos los algoritmos con acceso a un conjunto de oráculo arbitrario , al que suponemos que podemos hacer consultas de membresía, en un solo paso de cálculo. Una simulación paso-por-paso de A O x también puede ser llevado a cabo por A , siempre que A tiene acceso a la oráculo O también. En notación, tenemos T I M E O [ t ( n ) ] ⊊ T I M E O [ t ( n ) 2 ] para todos los oráculos $O$$A_x^O$$A$$A$$O$${\bf TIME}^O[t(n)] \subsetneq {\bf TIME}^O[t(n)^2]$$O$. En otras palabras, la jerarquía del tiempo se relativiza .

Podemos definir oráculos para máquinas no deterministas de forma natural, por lo que tiene sentido definir las clases y N P O con respecto a los oráculos. Pero hay oráculos O y O ′ en relación con los cuales P O = N P O y P O ′ ≠ N P O ′ , por lo que este tipo de argumento de simulación directa en el teorema de la jerarquía de tiempo no funcionará para resolver P versus N $P^O$$NP^O$$O$$O'$$P^O = NP^O$$P^{O'} \neq NP^{O'}$$P$$NP$. Los argumentos relativizadores son poderosos en el sentido de que son ampliamente aplicables y han dado lugar a muchas grandes ideas; pero este mismo poder que los hace "débil" con respecto a preguntas como frente al N P .$P$$NP$

Lo anterior es, por supuesto, un ejemplo de juguete: hay muchos otros ejemplos más complicados de argumentos en complejidad que aún se relativizan (es decir, se mantienen cuando se introducen oráculos arbitrarios).