cc.complexity-theory – ¿Existe un problema de computación que está en tiempo cuasi-polinomial pero (tal vez) no está en $ \ beta P $?

Pregunta:

El tiempo cuasi polinomial, o QP para abreviar, es una clase de complejidad en la máquina de Turing determinista. Aquí está la definición precisa: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

Mientras que βP es una clase de complejidad de no determinismo limitado. Aquí está la definición precisa: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Es fácil ver que cualquier máquina de βP puede ser simulada por una máquina de QP, a saber, βP $ \ subseteq $ QP.

Pero, ¿tenemos un ejemplo, un problema que está en QP pero no en βP, incluso si simplemente no tenemos una prueba precisa de que el problema no está en βP?

Respuesta:

Si bien no conozco un ejemplo específico (conjeturado) en $ QP- \ beta P $, todavía hay evidencia bastante convincente de que $ \ beta P $ es un subconjunto adecuado de $ QP $. Es decir, estas clases se comportan de manera muy diferente en su relación con $ NP $:

$ \ bullet $ Es obvio a partir de la definición que $ \ beta P \ subseteq NP $.

$ \ bullet $ Por otro lado, $ QP \ subseteq NP $ no se conoce y sería muy difícil de probar, ya que implica $ P \ neq NP $. (De hecho, es una declaración aún más fuerte que $ P \ neq NP $).

Un comportamiento tan diferente en relación con $ NP $ parece proporcionar una razón bastante sólida para creer que $ \ beta P \ neq QP $.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top

web tasarım