vollständiges Problem mit Quasipolynom, das an die Anzahl der Lösungen gebunden ist

FewP ist die Klasse der $NP$ -Probleme, bei denen das Polynom an die Anzahl der Lösungen (in der Eingabegröße) gebunden ist. Es ist kein $NP$ -vollständiges Problem in $fewP$ . Mich interessiert, wie weit wir diese Beobachtung ausdehnen können.

Gibt es ein natürliches $NP$ -vollständiges Problem mit quasi-polynomieller Obergrenze für die Anzahl der Lösungen (Zeugen)? Gibt es eine allgemein akzeptierte Vermutung, die eine solche Möglichkeit ausschließen würde?

Natürlich bedeutet, dass das Problem kein künstlich erfundenes Problem ist, um die Frage (oder ähnliche) zu beantworten, und dass die Menschen unabhängig (wie von Kaveh definiert) an dem Problem interessiert sind.

EDIT: Die Prämie wird für ein solches natürliches -vollständiges Problem oder ein vernünftiges Argument vergeben, das die Existenz solcher Probleme ausschließt (unter Verwendung allgemein akzeptierter komplexitätstheoretischer Vermutungen).$NP$

Motivation: Meine Intuition ist , dass -completeness erlegt Super-Polynom (oder sogar exponentiell) auf der Anzahl der Zeugen gebunden niedriger.$NP$

Das ist eine sehr interessante Frage.

Zunächst eine klarstellende Bemerkung. Es ist zu beachten, dass "Obergrenze für die Anzahl der Zeugen" keine Eigenschaft eines Rechenproblems an sich ist, sondern eines bestimmten Verifizierers, der zur Entscheidung eines Problems verwendet wird, ebenso wie "Obergrenze für die Anzahl der Zustände" keine Eigenschaft ist Eigentum eines Problems, aber einer Turing-Maschine, die es entscheidet. So sagen „ N P Problem obere auf der Anzahl der Lösungen gebunden mit“ nicht ganz richtig ist, und wenn P = N P dann alle N P Problem , einen Prüfer mit einer beliebigen Anzahl von gewünschten Lösungen (einschließlich Null und einschließlich aller möglichen Strings) hat .$NP$$NP$$P = NP$$NP$

Wir müssen also eine Definition vornehmen, um Ihre Frage zu beantworten. Für , sagen wir ein N P Problem L „hat höchstens s ( n ) Lösungen“ , wenn für eine Konstante c gibt es eine O ( n c ) Verifizierer V , so dass für jede Eingabelänge n und für jedes x ∈ L der Länge n gibt es verschiedene y 1 , … , y s ( $s : {\mathbb N} \rightarrow {\mathbb N}$$NP$$L$$s(n)$$c$$O(n^c)$$V$$n$$x \in L$$n$ der Länge n c, so dassV(x, y i )für alleiakzeptiertundV(x,y)alle anderenyder Länge n c zurückweist.$y_1,\ldots,y_{s(n)}$$n^c$$V(x,y_i)$$i$$V(x,y)$$y$$n^c$

Im Moment kann ich nur folgendes sagen:

1. Jedes -komplette Problem, das ich kenne (das von einem natürlichen Prüfer definiert wurde), hat eine offensichtliche korrespondierende # P -komplette Zählversion (mit demselben Prüfer).$NP$$\#P$
2. Für jedes -komplette Problem mit einem definierten Verifizierer mit höchstens p o l y ( n ) Lösungen (oder sogar 2 n o ( 1 ) Lösungen) die entsprechende Zählung Version ist wahrscheinlich nicht # P -komplette.$NP$$poly(n)$$2^{n^{o(1)}}$$\#P$

Weitere Details: Angenommen, ist N P -vollständig, mit einem Verifizierer V , der höchstens O ( n c ) -Lösungen aufweist. Dann die natürliche Zähl- "Entscheidungs" -Version von L , die wir als definieren$L$$NP$$V$$O(n^c)$$L$

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

ist berechenbar in , dh eine Polyzeitfunktion mit$FP^{NP[O(\log n)]}$ Anfragen an N P . Das liegt daranentscheidenob die Anzahl der Lösungen x höchstens k ist in N P : das Zeugnis, wenn es vorhanden, ist einfach die Anzahl von y i ‚s machen V akzeptieren, was wirwissenhöchstens sein O ( n c$O(\log n)$$NP$$x$$k$$NP$$y_i$$V$$O(n^c)$. Dann können wir eine binäre Suche unter Verwendung dieses Problems durchführen, um die genaue Anzahl von Lösungen für L zu berechnen .$NP$$L$

Ein solches -vollständiges Problem konnte daher nicht auf a erweitert werden$NP$auf die übliche Weise # P -Vollständigkeitsproblemwerden, es sei denn, # P ≤ F P N P [ O ( log n ) ] . Das sieht unwahrscheinlich aus. Die gesamte Polynomzeithierarchie würde im Grunde genommen zu P N P [ O ( log n ) ] zusammenfallen .$\#P$$\#P \subseteq FP^{NP[O(\log n)]}$$P^{NP[O(\log n)]}$

Wenn Sie oben von , erhalten Sie dennoch eine unwahrscheinliche Konsequenz. Sie würden zeigen , dass # P kann in berechnet werden 2 n o ( 1 ) Zeit mit einem N P Orakel. Das ist mehr als genug , um zu beweisen, zum Beispiel, dass E X P N P ≠ P P und anschließend E X P N P ⊄ P / p o l $s(n) = 2^{n^{o(1)}}$$\#P$$2^{n^{o(1)}}$$NP$$EXP^{NP} \neq PP$$EXP^{NP} \not\subset P/poly$. Nicht, dass diese Trennungen unwahrscheinlich wären, aber es scheint unwahrscheinlich, dass sie durch Angabe eines Subexp-Zeit- -Orakel-Algorithmus für die Permanente bewiesen würden .$NP$

Übrigens habe ich hier nichts zu Aufschlussreiches gesagt. Es gibt mit ziemlicher Sicherheit ein solches Argument in der Literatur.