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

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

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$$|L_n|$

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.$\varphi$$\lnot \varphi$

Deixe ser uma codificação que$\langle\ \rangle$

• para todas as fórmulas e para todas as atribuições de verdade τ ∈ { 0 , 1 } | & Phi; | , | ⟨ & Phi; ⟩ | = | ⟨ & Phi; , τ ⟩ | .$\varphi$$\tau \in \{0,1\}^{|\varphi|}$$|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$
• é computável em tempo polinomial.$|\langle\varphi\rangle| \mapsto |\varphi|$
• o número de fórmulas com comprimento codificado é computável em tempo polinomial.$n$

Considere

É 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 φ .$\varphi \in \mathsf{SAT}$

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^{|\varphi|}$$\tau$$\varphi$$\lnot \varphi$$\varphi$$2(2^{|\varphi|}+1)$$\langle\varphi\rangle$$\langle\lnot \varphi\rangle$$\langle\varphi, \tau\rangle$$\langle \lnot\varphi, \tau\rangle$. 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.$\tau \in \{0,1\}^{|\varphi|}$$2^{|\varphi|}$$2^{|\varphi|+1}+2$$L$$n$$L$$\varphi$$n$$2^{|\varphi|}$

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 \cap \{0,1\}^n| = 2^{n-1}$ is to explicitly build a bijection between $L \cap \{0,1\}^n$ and $\{0,1\}^n \backslash L$. Since I personally am not able to decide instances of $\mathsf{NP}$-hard problems, most "simple" bijections that I will come up with will have the form "$f\colon \{0,1\}^* \to \{0,1\}^*$ is a length-preserving bijection, and $x \in L$ if and only if $f(x) \notin L$." Furthermore, I'm likely to come up with such an $f$ that is computable in polynomial time. But then $\mathsf{NP} = \mathsf{coNP}$, for $f$ is a reduction from an $\mathsf{NP}$$\mathsf{coNP}$-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 $\mathsf{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 $\mathsf{coNP} \subseteq \mathsf{NTIME}(2^{(\log n)^{O(1)}}) =: \mathsf{NQP}$, from which I believe it follows by a simple induction with padding argument that $\mathsf{PH} \subseteq \mathsf{NQP}$. 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 $\mathsf{PH} \subseteq \mathsf{NQP}$, 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$?)