Czy istnieje język NP-complete, który zawiera dokładnie połowę n-bitowych instancji?

Czy istnieje (najlepiej naturalny) NP-pełny język $L\subseteq \{0,1\}^*$ , taki, że dla każdego $n\geq 1$

Zadałem to pytanie kilka lat temu i Boaz Barak odpowiedział na nie pozytywnie .

Stwierdzenie jest równoważne z istnieniem kompletnego języka NP gdzie | L n | jest obliczalny w czasie wielomianowym.$L$$|L_n|$

Rozważmy formuły logiczne i SAT. Używając dopełniania i nieznacznie modyfikując kodowanie formuł, możemy upewnić się, że i ¬ φ mają tę samą długość.$\varphi$$\lnot \varphi$

Niech być kodowanie$\langle\ \rangle$

• dla wszystkich formuł i dla wszystkich przypisań prawdy τ ∈ { 0 , 1 } | φ | , | ⟨ Cp ⟩ | = | ⟨ Cp , τ ⟩ | .$\varphi$$\tau \in \{0,1\}^{|\varphi|}$$|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$
• jest obliczalny w czasie wielomianowym.$|\langle\varphi\rangle| \mapsto |\varphi|$
• liczba wzorów o zakodowanej długości jest obliczalna w czasie wielomianowym.$n$

Rozważmy

Łatwo zauważyć, że jest NP-kompletny.$L$

Jeśli , liczba przypisań prawdy spełniających τ ⊨ φ  i  ∃ σ < τ σ ⊨ φ jest równa liczbie zadowalających przypisań prawdy - 1 . Dodając φ , sumuje się do liczby zadowalających przypisań prawdy dla φ .$\varphi \in \mathsf{SAT}$

Istnieją zadania prawdy. Każdy τ albo spełnia φ albo ¬ φ (i nie oba). Dla każdej formuły cp , rozważmy 2 ( 2 | cp | + 1 ) struny ⟨ φ ⟩ , ⟨ ¬ φ ⟩ , ⟨ φ , τ ⟩ i ⟨ ¬ φ , τ ⟩ dla τ ∈ { 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$. Dokładnie 2 | φ | z tych 2 | φ | + 1 + 2 łańcuchy są w L . Oznacza to, że liczba łańcuchów o długości n w L jest liczbą preparatów cp długości zakodowanego N pomnożone przez 2 | φ | który jest obliczalny w czasie wielomianowym.$\tau \in \{0,1\}^{|\varphi|}$$2^{|\varphi|}$$2^{|\varphi|+1}+2$$L$$n$$L$$\varphi$$n$$2^{|\varphi|}$

Here's a suggestion of why it might be difficult to come up with an example of such, though I agree with Kaveh's comment that it would be surprising if it didn't exist. [Not an answer, but too long for a comment.]

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}$-complete set to a $\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$?)