Existe uma linguagem NP-completa que contém precisamente metade das instâncias de n bits?

25

Existe uma linguagem NP completa (de preferência natural) L{0,1} , de modo que para cada seja ? Em outras palavras, contém precisamente metade de todas as instâncias de bits.n1 L n

|L{0,1}n|=2n1
Ln
Andras Farago
fonte
4
Seria muito surpreendente se não houvesse, mas pensar nisso por alguns minutos não conseguisse encontrar uma construção.
Kaveh
2
FWIW há uma tal que é NP-dura e em NP / POLI ...L
Neal Young
Para uma codificação binária bijetiva de fórmulas CNF, { e ( φ ) 1 | φ satisfatório } { e ( φ ) 0 | & Phi insatisfatível } deve funcionar. e{e(φ)1 | φ}{e(φ)0 0 | φ}
Klaus Draeger
4
@KlausDraeger A insatisfação não é uma propriedade NP, a menos que NP = co-NP.
Andras Farago
Existe alguma a Oracle tal que não existe LN P - C o m p L e T e S com esta propriedade? OLNPCompleteO
Erfan Khaniki

Respostas:

24

Eu fiz essa pergunta há alguns anos e Boaz Barak respondeu positivamente .


A declaração é equivalente à existência de uma linguagem NP completa onde | L n | é computável em tempo polinomial.L|Ln|

Considere fórmulas booleanas e SAT. Usando preenchimento e modificando ligeiramente a codificação das fórmulas, podemos garantir que e ¬ φ tenham o mesmo comprimento.φ¬φ

Deixe ser uma codificação que 

  • para todas as fórmulas e para todas as atribuições de verdade τ { 0 , 1 } | & Phi; | , | & Phi; | = | & Phi; , τ | .φτ{0,1}|φ||φ|=|φ,τ|
  • é computável em tempo polinomial.|φ||φ|
  • o número de fórmulas com comprimento codificado é computável em tempo polinomial.n

Considere

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

É fácil ver que é NP-completo.L

Se , o número de atribuições de verdade satisfazer τ & Phi;  e  σ < τ σ & Phi; é igual ao número de satisfazer as atribuições de verdade - 1 . Ao adicionar φ , ele soma o número de designações de verdade satisfatórias para φ .φSAT

τφ and σ<τ σφ
1φφ

Existem designações de verdade. Cada τ satisfaz φ ou ¬ φ (e não ambos). Para cada fórmula φ , considere a 2 ( 2 | φ | + 1 ) cordas φ , ¬ φ , φ , τ , e ¬ φ , τ para τ { 0 ,2|φ|τφ¬φφ2(2|φ|+1)φ¬φφ,τ¬φ,τ. Exatamente 2 | & Phi; | destes 2 | & Phi; | + 1 + 2 cordas estão em G . Isso significa que o número de cadeias de comprimento n em L é o número de fórmulas φ de comprimento codificado n multiplicado por 2 | & Phi; | qual tempo polinomial computável.τ{0,1}|φ|2|φ|2|φ|+1+2LnLφn2|φ|

Ryan O'Donnell
fonte
10
Mesmo que essa seja a solução desejada, essa é uma resposta distintamente apenas para links.
user2943160
para ficar claro, não há nada de especial no SAT, isso funcionaria com qualquer predicado de verificador para um problema de NP-completo.
Kaveh
@Kaveh, que você não usa aqui uma propriedade particular do SAT, que os casos vêm em pares , ¬ φ tal que qualquer testemunha τ é uma testemunha para exatamente um dos dois do par? Como você faria isso, por exemplo, 3-COLOR? ϕ¬ϕτ
Neal Young
@ Neal, permita que V (x, y) seja um verificador de um problema NP-completo. Considere W (x, b, y): = V (x, y) = b. Ainda é NP-completo e cada y é uma testemunha para x, 0 ou x, 1. Não é tão bom quanto SAT embora.
Kaveh
@Kaveh, e.g. with SAT are you suggesting
A={(ϕ,b,τ):(τ satisfies ϕ)b=1}?
But that is in P, and if you try to fix that by taking the union with, say, B={(ϕ,b):τSATb=1}, the union ABé NP-hard e co-NP-hard (provavelmente não no NP). EDIT: Ah, entendo, você quer fazer a união de com, digamos, C = { ( ϕ , b ) : τ . [ ( τ  satisfaz  ϕ ) b = 1 ] } ...AC={(ϕ,b):τ. [(τ satisfies ϕ)b=1]}
Neal Young
8

Aqui está uma sugestão de por que pode ser difícil criar um exemplo disso, embora eu concorde com o comentário de Kaveh de que seria surpreendente se não existisse. [Não é uma resposta, mas é muito tempo para comentar.]

Suppose that someone, say me, comes up with such a language L. A natural way for me to prove that L=n:=|L{0,1}n|=2n1 is to explicitly build a bijection between L{0,1}n and {0,1}nL. Since I personally am not able to decide instances of NP-hard problems, most "simple" bijections that I will come up with will have the form "f:{0,1}{0,1} is a length-preserving bijection, and xL if and only if f(x)L." Furthermore, I'm likely to come up with such an f that is computable in polynomial time. But then NP=coNP, for f is a reduction from an NPcoNP-complete one.

Of course, this objection can be gotten around by "simply" having the bijection be harder to compute than that. If your bijection takes exponential time - say it and its inverse might both be EXP-hard - then I think you're pretty safe. But if it only takes, say, quasi-polynomial time, then note that you still get the consequence coNPNTIME(2(logn)O(1))=:NQP, from which I believe it follows by a simple induction with padding argument that PHNQP. Now, if you believe the preceding containment is simply false, then no such quasi-poly-time computable bijection can save you. But even if you believe it might be true, then by coming up with such a bijection you would prove PHNQP, which seems to be beyond current knowledge...

The objection can also be gotten around by simply not having such a bijection, but then it seems harder to see how to prove that L has the desired property in the first place... And in fact, even if your proof isn't a bijection, you'd need it to be the case that no such easily computable bijection even exists.

Of course, this is also the type of thing where someone will come along with an example and we'll easily see how it gets around this objection, but I just wanted to throw this out there to say how anything with a simple enough bijection can't work (unless widely held beliefs are false).

(Related question: is there an oracle relative to which there is no such L?)

Joshua Grochow
fonte