¿Hay algún problema de computación que esté en tiempo cuasi-polinomial pero (tal vez) no esté en

El tiempo cuasi polinomial, o QP para abreviar, es una clase de complejidad en la máquina determinista de Turing. 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 QP. $\subseteq$

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

cc.complexity-theory complexity-classes Arthur Kexu-Wang
fuente

Sea f la función number_of_states_, y considere el problema "¿Se detiene M como máximo (f (M)) pasos? " .

$\hspace{2.36 in}$

^{\log (f (M))}

$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$

Respuestas:

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

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

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

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

Andras Farago
fuente

Además, parece poco probable que

se cierre bajo el complemento.

β P

$\beta P$

Emil Jeřábek

Dado que, como usted ha mencionado

implica

. Como seguimiento, ¿qué implicaría el resultado de

en la jerarquía de complejidad y tendría algún impacto en el problema

Q P \subseteq N P

$QP\subseteq NP$

P \neq N P

$P\neq NP$

N P \subseteq Q P

$NP \subseteq QP$

N P \subset Q P

$NP \subset QP$

P v s N P

$P vs NP$

TheoryQuest1

$\beta P$

Ver esta publicación relacionada .

Esta publicación de The CS Theory de @Salamon indica que ni siquiera sabemos si GI puede decidirse con un no determinismo acotado de raíz cuadrada y mucho menos con un no determinismo polilogarítmico.

Mohammad Al-Turkistany
fuente

Sin embargo, creo que mucha gente conjetura que el IG es en P.

Thomas

@Thomas Babai en su artículo indicó que está en contra de esta conjetura.

Mohammad Al-Turkistany

β P

$\beta P$

β P

$\beta P$

@JoshuaGrochow Sí, el comentario es más específico (señala la parte específica sobre el grado). Pero la respuesta solo hace referencia a la pregunta sobre MO como lo que considero una pista fuerte para la afirmación de que no hay pruebas, lo que me parece circular.

Clemente C.