En general, la cinta de consulta para un oráculo cuenta para la complejidad espacial de una TM. Sin embargo, parece plausible permitir una cinta de oráculo de solo escritura (como la que se usa en las reducciones de espacio L).
¿Es útil esta construcción? ¿Produce algún resultado particularmente absurdo?
cc.complexity-theory
space-bounded
oracles
Jeremy Hurwitz
fuente
fuente
Respuestas:
Creo que un hecho sorprendente es que, en este modelo, el teorema de Savitch no se relativiza "obviamente". Es decir, se puede ver que y N P S P A C E P = N E X P T I M E en este modelo, y actualmente no sepa que E X P T I M E = N E X P TPAGSPAGA CmiPAG= EXPAGTyoMETROmi nortePAGSPAGA CmiPAG= NmiXPAGTyoMETROmi (y el teorema de Savitch en este contexto no parece darlo). Me interesaría saber si esto puede ser empujado a "probablemente" no relativizar.miXPAGTyoMETROmi= NmiXPAGTyoMETROmi
También se puede observar que en este modelo.norteLnorteL=NLL=NPAG
Sin embargo, creo que al menos vale la pena pensar en este modelo, con respecto a los temas de relativización en el teorema de la jerarquía espacial. También, en cierto sentido, quiero para hacer consultas poli-tamaño a una .LUN UN
fuente
Es posible que esto no responda a su pregunta (que para ser sincero, no entiendo completamente), pero creo que está en el mismo espíritu. Se sabe que existe una diferencia en la reducibilidad entre un logspace TM con una cinta de oráculo y uno con acceso a múltiples cintas de oráculo. Además, la siguiente noción de espacio logarítmico tiene buenas propiedades: la TM solo puede usar una cantidad logarítmica de espacio en su cinta de trabajo, pero puede usar una cantidad polinómica de espacio en sus cintas oráculo.
Referencia: http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf
fuente
NSPACE (0) P = RE, lo que supongo que es un poco absurdo.
De hecho, dejemos que L sea un lenguaje recursivamente enumerable, M a TM que reconoce L y M ′ a TM que lee una entrada y un número n de "1" y luego simula M para esta entrada en n pasos. Luego, sin usar ningún espacio, podría copiar la entrada en la cinta Oracle, adivinar el número de 1 necesario y consultar M '.
Entonces, M 'aceptará si M acepta y tendrá una entrada lo suficientemente grande como para ser polinomial.
fuente