NP est-il dans

Réponses:

22

est appelé Q P (quasi-polynôme).DTIME(npolylogn)QP

Il est largement admis que , bien que ce soit une déclaration plus forte que P ≠ N P .NP⊄QPP≠NP

Quelques conjectures courantes, telles que le temps exponentiel Hypothesis impliquent .NP⊄QP

RB
la source
6
Vous dites que "Quelques conjectures courantes ...". Quels sont les autres à part ETH? Je suis extrêmement intéressé parce que je travaille actuellement sur les relations NP et QP - du moins je l'espère ...
Matt Groff
19

Une autre bonne raison de croire que est que N P ⊆ Q P implique E X P = N E X P , et ce dernier est hautement improbable. Cette implication peut être prouvée par un argument de remplissage, voir, par exemple, dans la preuve de la proposition 2 dans l'article suivant:NP⊈QPNP⊆QPEXP=NEXP

H. Buhrman et S. Homer, «Circuits superpolynomiaux, oracles presque clairsemés et hiérarchie exponentielle», Fondements de la technologie logicielle et de l'informatique théorique, Springer LNCS Vol. 652, 1992, p. 116-127, pdf

Andras Farago
la source
8
J'aime beaucoup cette réponse. Compte tenu de la réponse de RB, il me demande ce que, le cas échéant, est la relation entre l' ETH et l'hypothèse . EXP≠NEXP
Joshua Grochow
1
@Joshua Je n'ai pas cherché dans la littérature à ce sujet, mais je pense que toute violation des ETH implique probablement un effondrement à un niveau supérieur. Je suppose que le niveau dépend de "la force" avec laquelle l'ETH est violé, des violations plus fortes entraînant des effondrements plus dramatiques. Comme l' a souligné dans la réponse, la violation forte de l' ETH de implique E X P = N E X P . Si nous prenons une violation plus légère, comme en supposant que N P est dans une classe sous-exponentielle plus grande que Q P , alors l'effondrement est probablement déplacé vers le haut (par exemple, pour doubler les classes exponentielles ou même plus).NP⊆QPEXP=NEXPNPQP
Andras Farago
2
Thansk, mais je pose au sujet directe implication de toute façon entre ETH et . Nous avons maintenant deux réponses - ETH implique N P ⊈ Q P et N E X P ≠ E X P implique N P ⊈ Q P - et j'étais curieux de savoir si l'une était la conséquence de l'autre. EXP≠NEXPNP⊈QPNEXP≠EXPNP⊈QP
Joshua Grochow
2
Malheureusement, je n'ai pas connaissance d'une implication directe. Sur une autre note, il est assez intéressant de noter que les violations des ETH peuvent entraîner non seulement des effondrements, mais aussi des séparations, en termes de limites inférieures de circuit. Un article de Ryan Williams (pdf) prouve que même la moindre violation de l'ETH impliquerait notoirement difficile de prouver les limites inférieures du circuit.
Andras Farago