Existe-t-il un langage NP-complet qui contient précisément la moitié des instances de n bits?

25

Existe-t-il un langage NP (complet de préférence naturel) , tel que pour chaque détient? En d'autres termes, contient précisément la moitié de toutes les instances à bits.L{0,1}| L { 0 , 1 } n | = 2 n - 1 Ln1

|L{0,1}n|=2n1
Ln
Andras Farago
la source
4
Ce serait très surprenant s'il n'y en avait pas mais y penser pendant quelques minutes n'a pas pu trouver de construction.
Kaveh
2
FWIW il y a un tel qui est NP-dur et en NP / POLY ...L
Neal Young
Pour un codage binaire bijectif de formules CNF, { e ( φ ) 1 | φ satisfaisable } { e ( φ ) 0 | φ insatisfaisant } devrait fonctionner. e{e(φ)1 | φ}{e(φ)0 | φ}
Klaus Draeger
4
@KlausDraeger L'insatisfaction n'est pas une propriété NP, sauf si NP = co-NP.
Andras Farago
Existe-t-il un oracle tel qu'il n'existe pas LN P - C o m p l e t e O avec cette propriété? OLNPCompleteO
Erfan Khaniki

Réponses:

24

J'ai posé cette question il y a quelques années et Boaz Barak y a répondu positivement .


L'énoncé équivaut à l'existence d'un langage NP-complet | L n | est calculable en temps polynomial.L|Ln|

Considérez les formules booléennes et SAT. En utilisant un remplissage et en modifiant légèrement l'encodage des formules, nous pouvons nous assurer que et ¬ φ ont la même longueur.φ¬φ

Laissez être un codage 

  • pour toutes les formules et pour toute affectation de vérité τ { 0 , 1 } | φ | , | & Phiv | = | & Phiv , T permet | .φτ{0,1}|φ||φ|=|φ,τ|
  • est calculable en temps polynomial.|φ||φ|
  • le nombre de formules de longueur codée est calculable en temps polynomial.n

Considérons

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

Il est facile de voir que est NP-complet.L

Si , le nombre d'assignations de vérité satisfaisant τ φ  et  σ < τ σ φ est égal au nombre d'assignations de vérité satisfaisantes - 1 . En ajoutant φ lui-même, cela ajoute le nombre d'assignations de vérité satisfaisantes pour φ .φSAT

τφ and σ<τ σφ
1φφ

2|φ|τφ¬φφ2(2|φ|+1)φ¬φφ,τ¬φ,ττ{0,1}|φ|2|φ|2|φ|+1+2LnLφn2|φ|

Ryan O'Donnell
la source
10
Même s'il s'agit de la solution souhaitée, il s'agit d'une réponse distinctement liée uniquement aux liens.
user2943160
pour être clair, il n'y a rien de spécial à propos de SAT, cela fonctionnerait avec n'importe quel prédicat de vérificateur pour un problème NP-complet.
Kaveh
ϕ¬ϕτ
@Neal, que V (x, y) soit un vérificateur d'un problème NP-complet. Considérons W (x, b, y): = V (x, y) = b. Il est toujours NP-complet et chaque y est un témoin pour x, 0 ou x, 1. Pas aussi bien que SAT.
Kaveh
A={(ϕ,b,τ):(τ satisfies ϕ)b=1}?
B={(ϕ,b):τSATb=1}ABAC={(ϕ,b):τ. [(τ satisfies ϕ)b=1]}
8

Voici une suggestion de la raison pour laquelle il pourrait être difficile d'en trouver un exemple, même si je suis d'accord avec le commentaire de Kaveh selon lequel il serait surprenant que cela n'existe pas. [Pas une réponse, mais trop long pour un commentaire.]

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

Bien sûr, c'est aussi le genre de chose où quelqu'un viendra avec un exemple et nous verrons facilement comment cela contourne cette objection, mais je voulais juste jeter cela pour dire comment tout ce qui a une bijection assez simple peut 't work (sauf si les croyances largement répandues sont fausses).

L

Joshua Grochow
la source