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

15

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

Mohammad Al-Turkistany
quelle
1
Das Versprechen Problem UniqueSAT ist in (nicht die gleichen wie U P ), die eine Teilmenge von ist P r o m i s e F e w P (nicht die gleiche wie F e w P ) . PromiseUPUPPromiseFewPFewP
Joshua Grochow
3
Würde eine SAT-Polsterung Ihre Frage beantworten?
Kaveh
1
Das ist der springende Punkt - es ist nicht der springende Punkt; die Eingangsgröße ist die Anzahl der Bits im Eingangs und (sparse) 3-SAT - Instanzen Größe haben . Die Anzahl der Variablen ist nur ein Aspekt (Parameter) der Eingabe, daher müsste für andere Probleme (z. B. Diagrammprobleme) angegeben werden, inwieweit die Anzahl der Zeugen gemessen wird. Zum Beispiel kann der Eingabediagramm für max cut n 2 Kanten haben, und es gibt wiederum nur 2 n Zeugen (was in der Eingabegröße subexponentiell ist ). Aber wir wollen wirklich in n messen . Es ist jedoch nicht offensichtlich, dass #vertices das richtige Maß ist. mlognn22nn
Daniello
2
@Kaveh Ja, also solltest du annehmen, dass Mohammad an den gedacht hat, der in seiner Frage Sinn macht. Wie Sie sehen, stimmt der Komplexitätszoo auch mit meiner Definition überein. Im Allgemeinen sollte sich in einer interessanten Komplexitätsklasse die Definition nicht ändern, wenn Sie die Eingabe mit einem Polynom auffüllen.
Domotorp
5
@Downvoters Warum zum Teufel stimmen Leute diese Frage ab? Ich meine, zumindest könnte jemand einen Grund dafür nennen ...
domotorp

Antworten:

11

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 .NPNPP=NPNP

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 ( ns:NNNPLs(n)cO(nc)VnxLn der Länge n c, so dassV(x, y i )für alleiakzeptiertundV(x,y)alle anderenyder Länge n c zurückweist.y1,,ys(n)ncV(x,yi)iV(x,y)ync

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.NPpoly(n)2no(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 definierenLNPVO(nc)L

CountL(x):=the number of y such that V(x,y) accepts

ist berechenbar in , dh eine Polyzeitfunktion mitFPNP[O(logn)] 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(logn)NPxkNPyiVO(nc). 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 .NPL

Ein solches -vollständiges Problem konnte daher nicht auf a erweitert werdenNPauf 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#PFPNP[O(logn)]PNP[O(logn)]

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 PP P und anschließend E X P N PP / p o l ys(n)=2no(1)#P2no(1)NPEXPNPPPEXPNPP/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.

Ryan Williams
quelle
In der Tat ist es eine aufschlussreiche Antwort.
Mohammad Al-Turkistany