¿Se puede amplificar P = NP más allá de P = PH?

En Complejidad descriptiva , Immerman tiene

Corolario 7.23. Las siguientes condiciones son equivalentes:
1. P = NP.
2. Sobre estructuras finitas, ordenadas, FO (LFP) = SO.

Esto puede considerarse como "amplificación" de P = NP a un enunciado equivalente sobre (presumiblemente) clases de mayor complejidad. Tenga en cuenta que SO captura la jerarquía de tiempo polinomial PH, y que FO (LFP) captura P, por lo que esto puede considerarse como P = NP si P = PH.

(La parte interesante de esto es la afirmación de que P = NP implica P = PH; es trivial que P = CC implica P = NP para cualquier clase CC que contenga NP. Immerman simplemente comenta "si P = NP entonces PH = NP" , presumiblemente porque P = NP se puede usar con la definición del oráculo de PH para mostrar inductivamente que toda la jerarquía colapsa).

Mi pregunta es:

¿Cuánto más se puede amplificar P = NP de esta manera?

En particular, ¿cuál es la clase CC más grande conocida 'tal que P = NP implica P = CC', y la clase CC más pequeña tal que P = NP implica CC = NP? Esto permitiría reemplazar P = NP por la pregunta equivalente CC = CC '. P parece ser una clase bastante poderosa, que parece proporcionar poco "margen de maniobra" para los argumentos que intentan separarlo de NP: ¿hasta qué punto puede amplificarse el margen de maniobra?

Por supuesto, también me interesaría un argumento que muestre que P = PH es el límite de este enfoque.

Editar: tenga en cuenta la pregunta estrechamente relacionada ¿Por qué P = NP no implica P = AP (es decir, P = PSPACE)? que se centra en la otra dirección, por qué no tenemos pruebas de que P = PSPACE. Las respuestas de Kaveh y Peter Shor sostienen que la cantidad de alternancias que se arreglan es clave. Otra pregunta relacionada es un problema de decisión que no se sabe que está en PH pero estará en P si P = NP que solicita un problema candidato; las respuestas allí también pueden usarse para construir respuestas para esta pregunta, aunque estas clases son algo artificiales (gracias a Tsuyoshi Ito por señalar esto). En un entorno más general, colapso de la máquina de turing limitada por tiempo de espera y alternancia pregunta si un colapso local en cualquier nivel en una jerarquía de alternancia induce un colapso ascendente, como sucede con la jerarquía de tiempo polinomial.

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy András Salamon
fuente

Relacionados (autopromoción descarada): un problema de decisión que no se sabe que está en PH pero estará en P si P = NP .

Tsuyoshi Ito

Como una forma de formalizar qué idiomas están en P si P = NP, Regan introdujo la clase de complejidad H. Un lenguaje está en H si y solo si L está en P relación con cada oráculo para que P = NP . Por lo tanto, está en H si la afirmación P = NP P se relativiza. PH H Alternancia-tiempo . Del teorema de Toda, y algunos de los lemas del teorema de Toda, también es cierto que H P para cada . (Básicamente, cualquier oráculo que satisfaga P

L

$L$

^{O}

$^O$

O

$O$

^{O}

$^O$

^{O}

$^O$

L

$L$

⟹ L \in

$\implies L \in$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

(O (\log \log n), p o l y)

$(O(\log \log n), \rm{poly})$

\subseteq

$\subseteq$

^{{m o d}_{q} P}

$^{\rm{mod}_q \rm{P}}$

q

$q$

^{O}

$^O$ = NP da un nuevo límite superior en H. Está abierto si H = PH.)

^{O}

$^O$

Russell Impagliazzo

@Russell: gracias! Ese comentario suena como una respuesta.

András Salamon

Finalmente encontré una referencia a la clase Ken Regan : véase la definición 6.3 de "Conjuntos de índices y presentaciones de clases de complejidad", disponible en: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Versión oficial en: dx.doi.org/10.1016/0304-3975(95)00146-8

H

$H$

Joshua Grochow

Deje f (n) ser cualquier función sin límites. H no está contenido en Alternations-Time (f (n), poly) y si pudieras demostrar que P = NP implica P = Alternations-Time (f (n), poly) entonces NP es diferente de L.

Lance Fortnow

Respuestas:

Del comentario de Russell Impagliazzo :

Como una forma de formalizar qué idiomas hay en if , Regan introdujo la clase de complejidad . Un lenguaje es en si y sólo si es en relativa a cada oráculo de modo que . Por lo tanto, está en si la declaración relativiza. $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{H}$ $L$ $\mathsf{H}$ $L$ $\mathsf{P}^O$ $O$ $\mathsf{P}^O=\mathsf{NP}^O$ $L$ $\mathsf{H}$ $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$ . Desde el teorema de Toda, y algunos de los lemas del teorema de Toda, también es cierto que para cada . Básicamente, cualquier oráculo que satisfaga da un nuevo límite superior en . Está abierto si . $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ $q$ $\mathsf{P}^O=\mathsf{NP}^O$ $\mathsf{H}$ $\mathsf{H}=\mathsf{PH}$

Y del comentario de Lance Fortnow :

Deje ser cualquier función sin límites. no está contenido en y si pudiera probar implica luego es diferente de . $f(n)$ $\mathsf{H}$ $\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ $\mathsf{NP}$ $\mathsf{L}$

Para la definición de ver definición 6.3 en $\mathsf{H}$

Kenneth W. Regan, " Conjuntos de índices y presentaciones de clases de complejidad ", 1999

Kaveh
fuente

@Josh, con respecto al comentario de Lance, siento que me falta algo ya que no tiene límites y AltTime (f, poly) contiene H de acuerdo con el comentario de Russel.

f (n) = \lg \lg n

$f(n) = \lg \lg n$

Kaveh

Estoy confundido acerca de algo. ¿Por qué la respuesta de Josh Grochow a la pregunta anterior sobre este tema ( cstheory.stackexchange.com/a/2039/1575 ) tampoco responde esencialmente a la pregunta de Regan? Es decir, ¿por qué no da un ejemplo de un lenguaje L que está en P si P = NP por un argumento relativizante, pero que no está en PH si P! = NP? ¿Y por qué no muestra, por lo tanto, que si P! = NP, entonces H es estrictamente más grande que PH?

Scott Aaronson

En realidad, se me ocurre una posible respuesta. ¿Es el problema que, en la construcción de Grochow, la definición misma del lenguaje L dependerá del oráculo O?

Scott Aaronson

@Scott: De hecho, su posible respuesta es correcta, ya que las cadenas que se utilizan para la diagonalización (y, de hecho, si se ponen dentro o fuera de L) dependerá del oráculo. Más detalladamente, si , el lenguaje es finito, por lo que las diferentes para diferentes son solo finitamente diferentes. Pero si consideramos todo tal que , entonces la para estos diferentes ni siquiera puede ser equivalente a p, ya que este conjunto de oráculos es un subconjunto denso de .

P^{O} = N P^{O}

$P^O = NP^O$

L

$L$

L

$L$

O

$O$

O

$O$

P^{O} \neq N P^{O}

$P^O \neq NP^O$

L

$L$

O

$O$

2^{Σ^{*}}

$2^{\Sigma^*}$

Joshua Grochow

Como escribí en mi respuesta a la otra pregunta, hagamos que el argumento sea constructivo y uniforme en el número de alternancias dando un algoritmo que resuelva suponiendo que tenemos un algoritmo de tiempo polinómico para SAT y veamos qué obtendríamos si no es constante. $\Sigma^P_k$ $k$

Sea un DTM con dos entradas e . Piense en ello como un verificador para un problema . $M$ $x$ $y$ $\mathsf{NP}$

Deje que sea un algoritmo que convierta una TM en un circuito de tamaño que calcula en entradas de tamaño para pasos. $Cook(M, \vec{n}, t)$ $M$ $s(\vec{n},t) \in \mathsf{poly}$ $M$ $\vec{n}$ $t$

Suponga que y que existe un algoritmo determinista que resuelve el problema de extensión del certificado del Circuito SAT en el tiempo . $\mathsf{P}=\mathsf{NP}$ $A$ $p\in\mathsf{poly}$

Con estos ingredientes definimos un algoritmo para TQBF que, dada una fórmula booleana cuantificada, elimina recursivamente el cuantificador más interno y lo reemplaza por uno libre de cuantificadores. Supongamos que es el tamaño de la fórmula en el paso , entonces tenemos . Si la fórmula tiene cuantificadores, terminamos con donde es el tamaño de la fórmula TQBF dada como entrada. $s_i$ $i$ $s_{i+1} = s\circ p(s_i)$ $k$ $q(n) = (s \circ p)^k(n)$ $n$

Si es constante, entonces . Como el valor del circuito está en , tenemos un algoritmo de tiempo polinómico. $k$ $q(n) \in \mathsf{poly}$ $\mathsf{P}$

Si entonces ya no es tiempo polinomial, obtenemos un algoritmo que está en . Por ejemplo, si obtenemos un algoritmo de tiempo cuasipolinomial. Para no obtenemos nada no trivial. $k \in \omega(1)$ $q(n)$ $n^{2^{O(k)}}$ $k = \lg \lg n$ $k = \lg n$

Creo que lo que realmente nos interesa es la clase más grande de tal manera que donde es una teoría lo suficientemente fuerte como para formalizar toda nuestra corriente resultados (por ejemplo, puede tomarlo como ) porque el punto principal de estos resultados es facilitar la demostración de . $C$

T ⊢ P = N P \to P = C

$T \vdash \mathsf{P} = \mathsf{NP} \to \mathsf{P}=C$

T

$T$

Z F C

$\mathsf{ZFC}$

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

Si tomamos las teorías más débiles el resultado aún podría ser interesante, sin embargo, no es realmente un límite superior en el valor más grande de . Cuando Regan usa la relativización para definir , esencialmente está restringiendo los argumentos a aquellos que se relativizan. Si utilizamos un resultado que no se relativiza, podríamos obtener una clase más grande que que sería igual a si . $C$ $\mathsf{H}$ $\mathsf{H}$ $\mathsf{P}$ $\mathsf{P}=\mathsf{NP}$

Como nota más filosófica, personalmente no me gusta la idea de pensar en la relativización como realidades o mundos alternativos. Las declaraciones en "mundos relativizados" por sí mismas no nos dan ninguna información sobre la declaración en un entorno no relativizado. Como ejemplo de esto, tome que la mayoría de nosotros no creemos que sea cierto, pero la versión relativizada es verdadera wrt un oráculo aleatorio con probabilidad 1. Como otro ejemplo, tome que es cierto pero se convierte en falso wrt un oráculo aleatorio con probabilidad 1. $\mathsf{BPP} = \mathsf{PP}$ $\mathsf{IP} = \mathsf{PSpace}$

También encuentro que la idea de que hay una sola forma correcta de relativizar una clase de complejidad problemática que causa muchos conceptos erróneos (como pensar la relativización como una operación funcional en clases de complejidad en su sentido extensional, una relativización es una modificación de un modelo de computación , no una clase de funciones o idiomas). Creo que ver las relativizaciones como marcos de cálculo modificados (interactivos) es más útil. De esta manera, hay muchas formas útiles de relativizar las clases de complejidad (en su sentido intencional). Para obtener información sobre la configuración no relativizada de un marco relativizado, necesitamos algún tipo de principio de transferencia similar al principio de transferencia en análisis no estándar. Tenga en cuenta que elegir algún método particular de relativización para clases que preserven las relaciones conocidas entre clases no nos da un principio de transferencia (este es el criterio principal que se usa típicamente en la literatura para decidir cuál es "la" relativización correcta de una clase).

Kaveh
fuente

Estoy de acuerdo con "ver las relativizaciones como marcos de cálculo interactivos es más útil en mi opinión" de cierta manera. Es decir, la presentación de las relativizaciones podría hacerse más intuitiva de entender comenzando con la situación en la que las máquinas (con acceso interactivo al oráculo) se dan primero, y un oponente puede seleccionar un idioma para el oráculo. Luego uno cambia a la situación en la que primero se da un lenguaje de oráculo (complejo), y las máquinas ahora se pueden adaptar al mundo dado por el oráculo específico.

Thomas Klimpel