Gibt es eine NP-vollständige Sprache, die genau die Hälfte der n-Bit-Instanzen enthält?

25

Gibt es eine (vorzugsweise natürliche) NP-vollständige Sprache , so dass für jedes n 1 | L { 0 , 1 } n | = 2 n - 1 gilt? Mit anderen Worten enthält L genau die Hälfte aller n- Bit-Instanzen.L{0,1}n1

|L{0,1}n|=2n1
Ln
Andras Farago
quelle
4
Es wäre sehr überraschend, wenn es nichts gäbe, als ein paar Minuten darüber nachzudenken und keine Konstruktion zu finden.
Kaveh
2
FWIW gibt es so ein , das NP-hart ist und in NP / POLY ...L
Neal Young
Für eine bijektive binäre Codierung von CNF-Formeln gilt { e ( φ ) 1 | φ erfüllbar } { e ( φ ) 0 | φ unzufrieden } sollte funktionieren. e{e(φ)1 | φ}{e(φ)0 | φ}
Klaus Draeger
4
@KlausDraeger Unzufriedenheit ist keine NP-Eigenschaft, es sei denn, NP = co-NP.
Andras Farago
Gibt es ein Orakel so dass es mit dieser Eigenschaft kein LN P - C o m p l e t e O gibt? OLNPCompleteO
Erfan Khaniki

Antworten:

24

Ich habe diese Frage vor ein paar Jahren gestellt und Boaz Barak hat sie positiv beantwortet .


Die Aussage entspricht der Existenz einer NP-vollständigen Sprache wobei | L n | ist zur Polynomzeit berechenbar.L|Ln|

Betrachten Sie Boolesche Formeln und SAT. Durch Auffüllen und leichtes Ändern der Codierung von Formeln können wir sicherstellen, dass und ¬ φ die gleiche Länge haben.φ¬φ

Lassen Sie sein eine Codierung , dass 

  • für alle Formeln und für alle Wahrheitszuweisungen τ { 0 , 1 } | φ | , | & Phgr; | = | & Phgr; , & tgr; | .φτ{0,1}|φ||φ|=|φ,τ|
  • ist zur Polynomzeit berechenbar.|φ||φ|
  • Die Anzahl der Formeln mit der codierten Länge ist in Polynomzeit berechenbar.n

Betrachten

L:={φφSAT}{φ,ττφ and σ<τ σφ}

Es ist leicht zu erkennen, dass NP-vollständig ist.L

Wenn , die Anzahl der Wahrheits Zuteilungen & tgr; & phgr;  und  & sgr; < & tgr; & sgr; & phgr; ist gleich der Anzahl der Befriedigung Wahrheit Zuweisungen - 1 . Addiert man φ selbst, so addiert man die Anzahl der erfüllenden Wahrheitszuweisungen für φ .φSAT

τφ and σ<τ σφ
1φφ

Es gibt Wahrheitszuweisungen. Jedes τ erfüllt entweder φ oder ¬ φ (und nicht beide). Für jede Formel φ , sollten Sie die 2 ( 2 | φ | + 1 ) Saiten φ , ¬ φ , φ , & tgr; und ¬ φ , & tgr; für & tgr; & egr ; { 0 ,2|φ|τφ¬φφ2(2|φ|+1)φ¬φφ,τ¬φ,τ. Genau 2 | φ | davon 2 | φ | + 1 + 2 Strings sind in L . Dies bedeutet, dass die Anzahl der Ketten mit der Länge n in L die Anzahl der Formeln φ der codierten Länge n multipliziert mit 2 | ist φ | welche Polynomzeit berechenbar.τ{0,1}|φ|2|φ|2|φ|+1+2LnLφn2|φ|

Ryan O'Donnell
quelle
10
Auch wenn dies die gewünschte Lösung ist, handelt es sich um eine eindeutige Nur-Link-Antwort.
User2943160
Klar ist, dass SAT nichts Besonderes ist. Dies würde mit jedem Verifizierer-Prädikat für ein NP-vollständiges Problem funktionieren.
Kaveh
ϕ¬ϕτ
@Neal, sei V (x, y) ein Verifizierer für ein NP-vollständiges Problem. Betrachte W (x, b, y): = V (x, y) = b. Es ist immer noch NP-vollständig und jedes y ist ein Zeuge entweder für x, 0 oder x, 1. Nicht so schön wie SAT.
Kaveh
A={(ϕ,b,τ):(τ satisfies ϕ)b=1}?
B={(ϕ,b):τSATb=1}ABAC={(ϕ,b):τ. [(τ satisfies ϕ)b=1]}
8

Hier ist ein Vorschlag, warum es schwierig sein könnte, ein Beispiel dafür zu finden, obwohl ich Kavehs Bemerkung zustimme, dass es überraschend wäre, wenn es es nicht gäbe. [Keine Antwort, aber zu lang für einen Kommentar.]

LL=n:=|L{0,1}n|=2n1L{0,1}n{0,1}nLNPf:{0,1}{0,1}xLf(x)LfNP=coNPfNPcoNP

EXPcoNPNTIME(2(logn)O(1))=:NQPPHNQPPHNQP

L

Natürlich ist dies auch die Art von Dingen, bei denen jemand ein Beispiel vorstellt und wir werden leicht sehen, wie es um diesen Einwand geht, aber ich wollte dies nur rausschmeißen, um zu sagen, wie etwas mit einer ausreichend einfachen Bijektion kann funktioniert nicht (es sei denn, weit verbreitete Überzeugungen sind falsch).

L

Joshua Grochow
quelle