Techniken, um zu zeigen, dass das Problem in der Schwebe der Härte liegt

Angesichts eines neuen Problems in dessen wahre Komplexität irgendwo zwischen P und NP-vollständig liegt, gibt es zwei Methoden, von denen ich weiß, dass sie verwendet werden können, um zu beweisen, dass es schwierig ist, dies zu lösen:$\mathsf{NP}$$\mathsf{P}$

1. Zeigen Sie, dass das Problem GI-vollständig ist (GI = Graph Isomorphism)
2. Zeigen Sie, dass das Problem in . Nach bekannten Ergebnissen impliziert ein solches Ergebnis, dass, wenn das Problem NP-vollständig ist, PH auf die zweite Ebene zusammenbricht. Zum Beispiel macht das berühmte Protokoll für Graph Nonisomorphism genau das.$\mathsf{co-AM}$

Gibt es andere Methoden (möglicherweise mit unterschiedlichen "Glaubensstärken"), die angewendet wurden? Für jede Antwort ist ein Beispiel erforderlich, wo sie tatsächlich verwendet wurde: Natürlich gibt es viele Möglichkeiten, dies zu zeigen, aber Beispiele machen das Argument überzeugender.

Zu zeigen, dass Ihr Problem in coAM (oder SZK) liegt, ist in der Tat eine der Hauptmethoden, um Beweise für "Härteprobleme" zu liefern. Daneben gibt es aber noch einige andere:

• Zeigen Sie, dass Ihr Problem in NP ∩ coNP liegt. (Beispiel: Factoring.)
• Zeigen Sie, dass Ihr Problem in quasipolynomialer Zeit lösbar ist. (Beispiele: VC-Dimension, ungefähr kostenlose Spiele.)
• Zeigen Sie, dass Ihr Problem nicht schwerer ist, als Einwegfunktionen zu invertieren oder NP im Durchschnitt zu lösen. (Beispiele: Viele Probleme in der Kryptographie.)
• Zeigen Sie, dass sich Ihr Problem auf (z. B.) Unique Games oder Small-Set Expansion reduziert.
• Zeigen Sie, dass Ihr Problem in BQP liegt. (Beispiel: Faktorisierung, obwohl das natürlich auch in NP ∩ coNP ist.)
• Schließen Sie große Klassen von NP-Vollständigkeitsreduzierungen aus. (Beispiel: Das Schaltungsminimierungsproblem, das von Kabanets und Cai untersucht wurde.)

Ich bin sicher, es gibt andere, die ich vergesse.

Aus dem obigen Kommentar: Wenn ein Problem schwierig genug erscheint, Sie jedoch nicht nachweisen können, dass es NP-vollständig ist, müssen Sie die Anzahl der Zeichenfolgen mit der Länge in der Sprache schnell überprüfen : Wenn die Menge dünn ist, ist es Es ist unwahrscheinlich, dass es sich um einen NPC handelt, andernfalls ist P = NP nach Mahaneys Theorem$n$ besser, die Bemühungen darauf zu richten, zu beweisen, dass es sich um P handelt :-) :-)

Ein Beispiel ist das Problem der Aufteilung von Zahlen in K-Boxen (aus dem Fortnow & Gasarch-Blog, Originalquelle: Doctor Ecco's Cyberpuzzles ):

$\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

Hier sind drei Ergänzungen zu Scotts Liste:

• Zeigen Sie, dass Ihr Problem in fewP ist. Dies bedeutet, dass die Anzahl der Lösungen durch ein Polynom begrenzt ist. (Beispiel: Turnpike-Problem). Es ist kein NP-vollständiges Problem bei einigen P bekannt. (unmöglich, es sei denn, ein paar P = NP).
• Zeigen Sie, dass Ihr Problem vorliegt $LOGNP$ oder in $NP[log^2n]$ (Kann mit einer begrenzten Anzahl nichtdeterministischer Bits gelöst werden. Beispiel Dominierendes Set-Problem bei Turnieren.)
• Zeigen Sie, dass Ihr Problem eine subexponentielle Dichte hat (H. Buhrman und JM Hitchcock haben die untere Grenze der Dichte bewiesen ($2^{n^{\epsilon}}$), sofern die Polynomhierarchie nicht zusammenbricht. Daher keine$NP$-komplettes Set muss einiges haben $\epsilon \gt 0$ so dass für unendlich viele ganze Zahlen $n\ge 0$Das Set enthält mindestens $2^{n^{\epsilon}}$ Saiten von Länge $n$. ). Dies ist ein viel stärkerer Beweis als nur Sparsamkeit (wie in Marzios Antwort angegeben).

H. Buhrman und JM Hitchcock, NP-Hard Sets sind exponentiell dicht, es sei denn $coNP ⊆ NP/poly$, In der IEEE-Konferenz zu Computational Complexity, Seite 1–7, 2008