Probleme außerhalb von P, die nicht P-hart sind

Als ich eine Antwort von Peter Shor und eine frühere Frage von Adam Crume las, stellte ich fest, dass ich einige falsche Vorstellungen darüber habe, was es bedeutet, hart zu sein. $\mathsf{P}$

Ein Problem ist hart, wenn ein Problem in mit Reduktionen (oder wenn Sie Reduktionen bevorzugen ) auf reduziert werden kann . Ein Problem liegt außerhalb von wenn kein polynomieller Zeitalgorithmus existiert, um es zu lösen. Dies bedeutet, dass es Probleme geben sollte, die außerhalb von aber nicht hart sind. Wenn wir annehmen, dass FACTORING außerhalb von , deutet die Antwort von Peter Shor darauf hin, dass FACTORING ein solches Problem sein könnte. $\mathsf{P}$ $\mathsf{P}$ $\mathsf{L}$ $\mathsf{NC}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$

Gibt es bekannte (natürliche oder künstliche) Probleme, von denen bekannt ist, dass sie außerhalb von aber nicht hart sind? Was ist mit Annahmen, die schwächer sind als die Faktorisierungsannahme? Gibt es einen Namen für diese Komplexitätsklasse? $\mathsf{P}$ $\mathsf{P}$

cc.complexity-theory complexity-classes Artem Kaznatcheev
quelle

Antworten:

Wenn ist, kann keine dünne Menge (auch keine nicht berechenbare) . $\mathsf{P} \neq \mathsf{L}$ $\mathsf{P\text{-}hard}$

Das Missverständnis entsteht, wenn Komplexitätsklassen (und Rechenprobleme) als eine lineare Ordnung betrachtet werden, die nicht wahr ist. Die Verwendung des Wortes "Härte" für ein Problem kann verwendet werden, um andere Probleme in der Klasse zu lösen, was ebenfalls zu dem Missverständnis beiträgt. Eine Untergrenze für ein Problem (dh nicht in einer Komplexitätsklasse) bedeutet nicht, dass das Problem für die Klasse schwierig ist (dh zur Lösung anderer Probleme in der Klasse verwendet werden kann). Ich weiß nicht, ob es eine bessere alternative Terminologie für "Härte" gibt, die derzeit verwendet wird. Eine, die in den letzten Jahrzehnten verwendet wurde, ist "Universalität" (die, meiner Meinung nach, das Konzept getreuer ausgedrückt hat und die wir dann hätten verwenden können "Härte", wenn man nicht in der Klasse ist, aber die etablierte Terminologie ändert, ist sehr schwierig).

Kaveh
quelle

Einige der Euler-Diagramme, die ich von Komplexitätsklassen gesehen habe, haben auch das zweite Missverständnis für mich ausgelöst, was meiner Meinung nach meine Verwirrung über die X-Härte verursacht hat.

Artem Kaznatcheev

@Artem, ja, das ist auch ein Faktor. Hier ist, was ich in der Klasse mache: Ich erwähne die Unvergleichbarkeit von und unter -Reduktionen, in der Hoffnung, dass dies den Schülern helfen würde, nicht zu , dass alles linear geordnet ist.

\mod p

$\mod p$

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Kaveh

Mit dem gesamten Bestellteil habe ich viel weniger Probleme. Insbesondere denke ich, dass NP und coNP gut genug sind, um zu zeigen, dass wir nicht an Komplexitätsklassen mit einer Gesamtordnung denken sollten.

Artem Kaznatcheev

@Artem, guter Punkt (obwohl wir nicht beweisen können, dass sie unterschiedlich sind). Ich denke, ein Teil des Grundes für die Terminologie ist das Fehlen vernünftiger Untergrenzen. Wir haben keine gute Untergrenze für SAT, aber wir denken, dass es schwierig zu lösen ist, weil es universell ist, aber das Wort "universal" nicht geben das gleiche Gefühl der Schwierigkeit wie "schwer", vor allem für Nicht-Experten. Aber das schafft das Problem, denn obwohl man argumentieren kann, dass die Universalität eines Problems impliziert, dass das Problem schwer zu lösen ist, impliziert die Schwierigkeit, ein Problem zu lösen, nicht, dass das Problem universell ist.

Kaveh

Das heißt, universelle Probleme sind schwierig (mindestens so schwierig wie jedes Problem in der Klasse), aber schwierige Probleme müssen nicht universell sein.

Kaveh

Ich denke, Sie können eine Menge erstellen, die nicht in ist und die nicht hard ist. Hier ist ein konkretes Beispiel. $P$ $P$

In seiner Arbeit "Ein einheitlicher Ansatz zur Ermittlung von Diagonalsätzen in Komplexitätsklassen" (Theor. Comp. Sci. 18, 1982) beweist Schöning Folgendes:

Theorem Angenommen, , , und sind rekursiv darstellbare Komplexitätsklassen und werden unter endlichen Variationen geschlossen. Dann gibt es noch eine Reihe , so dass , , und wenn und ist nicht trivial (leere Menge oder alle Strings) dann polytime many-one reduzierbar ist . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

Zur Anwendung dieses, Set die leere Menge zu sein, und sein -komplette unter polytime Senkungen gesetzt die Menge von -hard - Sets , die in sind , setzen . Die leere Menge darf nicht hart sein (die Definition der Härte für eine Sprache setzt voraus, dass mindestens eine Instanz in der Sprache und eine Instanz nicht in vorhanden ist). ist definitiv nicht in . Die und können die oben genannten Bedingungen (ähnlich gerecht zu werden überprüft werden , wie Schoening tut es für die $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ $C_2$ $NP$ -komplette Sätze; siehe auch diese verwandte Frage ). Wir bekommen also ein , das kein hartes Problem in , und dass nicht in . Aber da und nichttrivial ist, ist um ein Vielfaches auf eine vollständige Menge reduzierbar , also ist es in . Daher kann insbesondere auch nicht hart sein. $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ $P$

In dem obigen Argument ist die Beschränkung auf -harte Probleme in notwendig, um eine rekursive Darstellbarkeit sicherzustellen, da die P-harten Probleme insgesamt nicht rekursiv darstellbar und nicht einmal abzählbar sind . Nun, "natürliche" Beispiele dafür sind eine andere Geschichte ... $P$ $EXP$

Ryan Williams
quelle

Ich mag , wie das geht durch , auch wenn . Es sei denn, ich habe etwas falsch verstanden.

L = P

$L = P$

Artem Kaznatcheev

@Artem: Wenn Sie die Härte bei der Reduzierung des Protokollbereichs berücksichtigen, ist jede nichttriviale Sprache L-hart. Wenn daher L = P ist, gibt es keine Sprachen außerhalb von P, die unter der Log-Space-Reduzierbarkeit P-hart sind.

Tsuyoshi Ito

Eine andere Möglichkeit, Probleme zu generieren, die außerhalb von P liegen, aber nicht P-schwer sind, besteht darin, vollständige Probleme für Klassen zu übernehmen, die nicht mit P vergleichbar sind. Dann liegt ein X-vollständiges Problem notwendigerweise außerhalb von P (andernfalls würde P X einschließen) und ist nicht P-hart (andernfalls würde X P einschließen).

Ich habe versucht, mir einige Klassen vorzustellen, die mit P nicht zu vergleichen sind, aber P ist eine ziemlich robuste Klasse, daher gibt es nicht allzu viele solcher Klassen. Beispielsweise sind RNC und QNC möglicherweise nicht mit P. vergleichbar. DSPACE ( ) ist möglicherweise auch nicht mit P. PolyL ist nicht mit P vergleichbar, hat jedoch keine vollständigen Probleme bei der Reduzierung des Protokollbereichs. $\log^2$

Robin Kothari
quelle

Meiner Meinung nach ist dies fast dieselbe Frage, die anders formuliert ist, und es ist nicht unbedingt eine Möglichkeit, die Frage zu beantworten. Tatsächlich ist Sprache A nur dann weder in P noch in P-schwer, wenn die Klasse der Sprachen, die auf A reduziert werden kann, mit P nicht zu vergleichen ist (nehmen Sie Ihren Lieblingsbegriff von Reduzierbarkeit). Solange es die aktuelle Frage betrifft, denke ich, ist es wahrscheinlicher, dass sie in die entgegengesetzte Richtung nützlich ist. Das heißt, dies ist eine andere Möglichkeit, die Antworten auf die aktuelle Frage zu interpretieren.

Tsuyoshi Ito