NP-vollständiges Problem mit einer Polynomzahl von Ja-Instanzen?

Ich habe den Eindruck, dass für jedes NP-vollständige Problem für unendlich viele Eingabegrößen die Anzahl der Ja-Instanzen über alle möglichen Eingaben der Größe n (mindestens) exponentiell in n ist .$n$$n$$n$

Ist das wahr? Kann es bewiesen werden (wahrscheinlich nur unter der Annahme, dass )? Oder können wir vielleicht künstlich ein Problem finden, bei dem für alle (ausreichend großen) n die Anzahl der Ja-Instanzen in n höchstens polynomiell ist ?$P\neq NP$$n$$n$

Meine Überlegung ist im Grunde genommen, dass wir bei einer Ja-Instanz für 3-SAT das Literal in jeder Klausel identifizieren können, das sie wahr macht, und eine andere Variable in der Klausel durch eine weitere Variable ersetzen können, ohne zu ändern, dass es erfüllbar ist. Da dies mit jeder Klausel möglich ist, führt dies zu einer exponentiellen Anzahl von Ja-Instanzen. Das Gleiche gilt für viele andere Probleme wie den Hamilton-Pfad: Wir können Kanten, die sich nicht auf dem Pfad befinden, frei ändern. Ich begründe dann vage, dass, da es um Reduzierbarkeit geht, wo in gewisser Weise Lösungen eingehalten werden müssen, diese für alle NP-vollständigen Probleme gelten muss.

Dies scheint auch für das möglicherweise NP-intermediäre Problem der Graphisomorphie zu gelten (bei dem wir die gleichen Änderungen auf beide Graphen anwenden können, wenn wir die Abbildung kennen). Ich frage mich, ob es auch für die ganzzahlige Faktorisierung gilt.

Eine Sprache mit nur polynomiell vielen Ja-Instanzen wird als spärlich bezeichnet . Mahaneys Theorem besagt, dass wenn eine NP-vollständige Sprache spärlich ist, P = NP ist. Da die meisten Leute P NP erwarten, ist es unwahrscheinlich, dass es eine NP-vollständige Sprache mit nur polynomiell vielen Ja-Instanzen gibt.$\ne$

Es ist eine separate Frage, ob die Anzahl der Ja-Instanzen exponentiell ist. (Man könnte sich vorstellen, dass die Anzahl der Ja-Instanzen mehr als polynomial, aber weniger exponentiell ist.) Die Berman-Hartmanis-Vermutung ist hier relevant; es impliziert, dass alle NP-vollständigen Probleme exponentiell viele Ja-Instanzen haben. Die Vermutung bleibt ein offenes Problem.