Ist NP in

Antworten:

22

DTIME(npolylogn) ist bekannt alsQP (Quasi-Polynom) .

Es wird allgemein angenommen, dass NP⊄QP , obwohl es eine stärkere Aussage ist alsP≠NP .

Einige verbreitete Vermutungen, wie die Exponential Time Hypothesis, implizieren .NP⊄QP

RB
quelle
6
Sie sagen, dass "Einige häufige Vermutungen ...". Was sind die anderen ausser der ETH? Ich bin sehr interessiert, weil ich gerade daran arbeite, NP und QP in Beziehung zu setzen - zumindest hoffe ich das ...
Matt Groff
19

Ein weiterer guter Grund zu der Annahme, dass ist, dass impliziert , und letzteres wird als höchst unwahrscheinlich angesehen. Diese Implikation kann durch ein Auffüllargument bewiesen werden, siehe z. B. den Beweis von Satz 2 in der folgenden Abhandlung:N P ⊆ Q P E X P = N E X PNP⊈QPNP⊆QPEXP=NEXP

H. Buhrman und S. Homer, "Superpolynomschaltungen, fast spärliche Orakel und die exponentielle Hierarchie", Grundlagen der Softwaretechnologie und der theoretischen Informatik, Springer LNCS Vol. 652, 1992, S. 116-127, pdf

Andras Farago
quelle
8
Ich mag diese Antwort sehr. Angesichts der Antwort von RB frage ich mich, wie die Beziehung zwischen der ETH und der Annahme . EXP≠NEXP
Joshua Grochow
1
@Joshua Ich habe nicht in der Literatur nachgeschlagen, aber ich denke, jede Verletzung der ETH impliziert wahrscheinlich einen Zusammenbruch auf einer höheren Ebene. Ich denke, der Level hängt davon ab, "wie stark" die ETH verletzt wird, wobei stärkere Verstöße zu dramatischeren Einbrüchen führen. Wie in der Antwort darauf hingewiesen, die starke ETH Verletzung von impliziert E X P = N E X P . Wenn wir eine mildere Verletzung annehmen, beispielsweise die Annahme, dass N P in einer subexponentiellen Klasse liegt, die größer ist als Q PNP⊆QPEXP=NEXPNPQP , wird der Kollaps wahrscheinlich nach oben verschoben (z. B. zu doppelt exponentiellen Klassen oder sogar höher).
Andras Farago
2
Thansk, aber ich habe nach einer direkten Beziehung zwischen ETH und gefragt . Wir haben jetzt zwei Antworten - ETH impliziert N P ⊈ Q P und N E X P ≠ E X P impliziert N P ⊈ Q P - und ich war gespannt, ob eines eine Konsequenz des anderen ist. EXP≠NEXPNP⊈QPNEXP≠EXPNP⊈QP
Joshua Grochow
2
Leider ist mir keine direkte Auswirkung bekannt. Zum anderen ist es interessant, dass ETH-Verstöße nicht nur Kollaps, sondern auch Trennungen in Bezug auf die Schaltkreisuntergrenzen zur Folge haben können. Ein Artikel von Ryan Williams (pdf) beweist, dass selbst die geringste Verletzung der ETH-Richtlinien den Nachweis von Schaltkreisuntergrenzen mit sich bringen würde.
Andras Farago