¿Por qué no usamos clases más grandes para estudiar determinismo versus no determinismo?

En una pregunta anterior sobre la jerarquía de tiempo, aprendí que las igualdades entre dos clases se pueden propagar a clases más complejas y las desigualdades se pueden propagar a clases menos complejas, con argumentos que utilizan relleno.

Por lo tanto, una pregunta viene a la mente. ¿Por qué estudiamos una pregunta sobre los diferentes tipos de cómputo (o recursos) en la clase más pequeña (cerrada) posible?

La mayoría de los investigadores creen que . Esta distinción de clases no sería entre clases que usan el mismo tipo de recurso. Por lo tanto, uno podría pensar en esta desigualdad como una regla universal: el no determinismo es un recurso más poderoso. Por lo tanto, aunque es una desigualdad, podría propagarse hacia arriba mediante la explotación de la naturaleza diferente de los dos recursos. Por lo tanto, uno podría esperar que también. Si se probara esta relación o cualquier otra desigualdad similar, se traduciría a .E X P ≠ N E X P P ≠ N $P \neq NP$$EXP \neq NEXP$$P \neq NP$

Mi argumento tal vez podría aclararse en términos de física. Newton tendría dificultades para comprender la gravedad universal al examinar rocas (¿manzanas?) En lugar de cuerpos celestes. El objeto más grande ofrece más detalles en su estudio, dando un modelo más preciso de su comportamiento y permitiendo ignorar fenómenos a pequeña escala que podrían ser irrelevantes.

Por supuesto, existe el riesgo de que en objetos más grandes haya un comportamiento diferente, en nuestro caso, que el poder extra del no determinismo no sería suficiente en clases más grandes. ¿Qué pasa si después de todo, está probado? ¿Deberíamos comenzar a trabajar en al día siguiente?E X P ≠ N E X $P \neq NP$$EXP \neq NEXP$

¿Considera que este enfoque es problemático? ¿Conoces alguna investigación que use clases más grandes que el polinomio para distinguir los dos tipos de cómputo?

El problema puede ser un poco más limpio con y . La forma más fácil de pensar acerca de estas clases es que son las mismas que y pero están restringidas a los idiomas unarios . Es decir, todas las entradas son de la forma .N E = N t i m e ( 2 O ( n ) ) P N P 1 $E=Dtime(2^{O(n)})$$NE=Ntime(2^{O(n)})$$P$$NP$$1^k$

Es decir, el lenguaje está en si y solo si el lenguaje está en (identificando cadenas con números usando representación binaria), y de manera similar es isomorfo a unario .E U L = { 1 x : x ∈ L } P N E N $L$$E$$U_L = \{ 1^x : x\in L \}$$P$$NE$$NP$

Por lo tanto, tratar de separar de es como tratar no solo de separar de , sino también hacerlo usando un lenguaje unario. No hay razón para que tu vida sea aún más fácil conceptualmente.E P N $NE$$E$$P$$NP$

¿Por qué elegimos preocuparnos por vs. ? En realidad, el no determinismo como objeto de estudio es solo una preocupación secundaria. Realmente nos importa debido a los miles de problemas importantes que son completos. Estos son problemas que queremos (y en la vida real necesitamos resolver). Nos preocupamos si estos problemas se pueden resolver de manera eficiente, y es nuestro modelo teórico para el cálculo eficiente. Por lo tanto, nos llevan a la pregunta de vs. .N P N P N P P P N $P$$NP$$NP$$NP$$P$$P$$NP$

Tenga en cuenta que existen separaciones conocidas para algunas clases de complejidad ilimitadas, por ejemplo, , y también igualdades como N P S p a c e = P S p a c e y p r $decidable \neq computability \ enumerable$$NPSpace = PSpace$$primitive \ recursive = nondeterministic \ primitive \ recursive$. (Es interesante pensar en por qué el relleno trivial usarlos no es útil para la solución de P vs NP.) Debemos tener más cuidado con lo que entendemos por una pregunta como vs N P y E X P vs N E X P . Si P vs N P es una versión acolchada (p. Ej. E X P vs N E X P y E vs N E ), entonces la respuesta de Boaz también se aplicará.$P$$NP$$EXP$$NEXP$$P$$NP$$EXP$$NEXP$$E$$NE$

La evidencia de es mucho más débil que P ≠ N P y tiene consecuencias menos dramáticas, y hay personas que consideran plausible E X P = N E X P, por lo que la situación es más complicada allí y tenemos Una intuición mucho más débil sobre la respuesta esperada. Una igualdad no ayudará en la práctica y no se sabe que tenga un efecto en el caso realmente interesante que es P vs N P , y una desigualdad es formal y conceptualmente tan difícil como una desigualdad entre$EXP \neq NEXP$$P \neq NP$$EXP = NEXP$$P$$NP$ vs N P .$P$$NP$