¿Está NP en

Respuestas:

22

se conoce como Q P (cuasi-polinomial).DTIME(npolylogn)QP

Se cree ampliamente que , aunque es una declaración más fuerte que P ≠ N P .NP⊄QPP≠NP

Algunas conjeturas comunes, tales como la exponencial Tiempo Hipótesis implican .NP⊄QP

RB
fuente
66
Dices que "Algunas conjeturas comunes ...". ¿Cuáles son los otros además de ETH? Estoy extremadamente interesado porque actualmente estoy trabajando en relacionar NP y QP, al menos eso espero ...
Matt Groff
19

Otra buena razón para creer que es que N P ⊆ Q P implica E X P = N E X P , y esto último se considera altamente improbable. Esta implicación puede probarse mediante un argumento de relleno, véase, por ejemplo, en la prueba de la Proposición 2 en el siguiente documento:NP⊈QPNP⊆QPEXP=NEXP

H. Buhrman y S. Homer, "Circuitos superpolinomiales, oráculos casi dispersos y la jerarquía exponencial", Fundamentos de la tecnología del software y la informática teórica, Springer LNCS vol. 652, 1992, pp. 116-127, pdf

Andras Farago
fuente
8
Me gusta mucho esta respuesta. Teniendo en cuenta la respuesta de RB, eso me hace pensar lo que, en su caso, es la relación entre ETH y la asunción . EXP≠NEXP
Joshua Grochow
1
@Joshua No busqué en la literatura sobre esto, pero creo que cualquier violación de ETH probablemente implique algún colapso en un nivel superior. Supongo que el nivel depende de "qué tan fuerte" se viola el ETH, violaciones más fuertes que producen colapsos más dramáticos. Como se señala en la respuesta, la fuerte violación de ETH implica E X P = N E X P . Si tomamos una violación más leve, como suponer que N P está en una clase subexponencial mayor que Q P , entonces el colapso probablemente se desplaza hacia arriba (por ejemplo, a clases exponenciales dobles o incluso más altas).NP⊆QPEXP=NEXPNPQP
Andras Farago
2
Thansk, pero yo estaba preguntando por una directa implicación de cualquier manera entre ETH y . Ahora tenemos dos respuestas: ETH implica N P ⊈ Q P y N E X P ≠ E X P implica N P ⊈ Q P - y tenía curiosidad por saber si una era consecuencia de la otra. EXP≠NEXPNP⊈QPNEXP≠EXPNP⊈QP
Joshua Grochow
2
Lamentablemente, no tengo conocimiento de una implicación directa. En otra nota, es bastante interesante que las violaciones de ETH pueden producir no solo colapsos, sino también separaciones, en términos de límites inferiores del circuito. Un artículo de Ryan Williams (pdf) demuestra que incluso la más mínima violación de ETH implicaría ciertos límites inferiores notoriamente difíciles de probar.
Andras Farago