Ist es einfach, einfache Fälle von NP-harten Problemen zu erkennen?

Meine Frage lautet wie folgt. Angenommen, ist ein NP-hartes Problem. Ist es bei einer beliebigen Instanz I von Π und der Annahme, dass ein Gegner weiß, dass diese Instanz leicht zu lösen ist, möglich, einen deterministischen Polynom-Zeit-Algorithmus zu finden, um diese bestimmte Instanz I zu lösen ?$\Pi$$I$$\Pi$$I$

Zum Beispiel: Angenommen, ist GRAFIKFARBE. Der Gegner gibt Ihnen einen Graphen G mit n Eckpunkten.$\Pi$$G$$n$

1. Der Gegner weiß, dass vollständig ist, aber Sie nicht. Können Sie einen Polynom-Zeit-Algorithmus finden, der besagt: "Dieser Graph ist mit Δ + 1 Farben färbbar "?$G$$\Delta +1$
2. Der Gegner weiß, dass eine Eigenschaft P hat, aber Sie nicht. Können Sie einen Polynom-Zeit-Algorithmus finden, der besagt: "Dieser Graph ist mit b- Farben färbbar "?$G$$P$$b$
3. ...

$S$$S$$S$$I$

Daher lautet die Antwort auf Ihre Frage "Ja", jedoch aus uninteressanten Gründen. Möglicherweise müssen Sie mehr darüber nachdenken, wie Sie Ihre Frage so formulieren können, dass sie dem entspricht, was Sie wirklich wissen möchten.

$I$$\Pi$

Schließlich weiß ich nicht, was es bedeutet zu sagen "Der Gegner kennt X, aber Sie nicht". Es steht mir frei, einen Algorithmus zu schreiben, der davon ausgeht, dass X wahr ist und nur funktioniert, wenn X wahr ist. "Wissen" ist eine lustige Sache und nicht gut modelliert durch die Art von Werkzeugen, über die Sie zu sprechen scheinen; In der Komplexitätstheorie geht es mehr um "Existenz" als um "Wissen".

In gewissem Sinne ist die Antwort auf Ihre Frage aufgrund des universellen Suchalgorithmus von Levin positiv. Berücksichtigen Sie für die Konkretheit die Farbgebung der Diagramme und eine bestimmte Klasse einfacher Instanzen. Als Zeuge dafür, dass diese Klasse einfach ist, haben Sie einen Algorithmus, der anhand eines Diagramms in dieser Klasse (in Polynomzeit) eine legale Färbung zusammen mit einem Polynomgrößenbeweis erzeugt, der beweist, dass die Färbung optimal ist.

Der universelle Suchalgorithmus von Levin führt alle Polynomzeitalgorithmen auf seiner Instanz aus (dies wird erreicht, indem alle möglichen Polynomzeitgrenzen für jeden Algorithmus ausprobiert werden) und überprüft, ob sie eine legale Färbung zusammen mit einem Optimalitätsnachweis liefern. In jeder Klasse einfacher Instanzen wird dieser Algorithmus in Polynomzeit ausgeführt. Leider werden die Konstanten sehr groß sein, so dass dieser Algorithmus nicht praktikabel ist.