Is there an NP-complete language that contains precisely half of the n-bit instances?

Question

Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$ $$|L\cap \{0,1\}^n|=2^{n-1}$$ holds? In other words, $L$ contains precisely half of all $n$-bit instances.

Answer 1

I asked this question a few years ago and Boaz Barak positively answered it.

---

The statement is equivalent to the existence of an NP-complete language $L$ where $|L_n|$ is polynomial-time computable.

Consider Boolean formulas and SAT. Using padding and slightly modifying the encoding of formulas we can make sure that $\varphi$ and $\lnot \varphi$ have the same length.

Let $\langle\ \rangle$ be an encoding that

• for all formulas $\varphi$ and for all truth assignment $\tau \in \{0,1\}^{|\varphi|}$, $|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$.
• $|\langle\varphi\rangle| \mapsto |\varphi|$ is polynomial-time computable.
• the number of formulas with encoded length $n$ is polynomial-time computable.

Consider $$L := \{\langle\varphi\rangle \mid \varphi \in \mathsf{SAT} \} \cup \{\langle \varphi, \tau \rangle \mid \tau \vDash \varphi \text{ and } \exists \sigma<\tau\ \sigma\vDash\varphi \}$$

It is easy to see that $L$ is NP-complete.

If $\varphi \in \mathsf{SAT}$, the number of truth assignments satisfying $$\tau \vDash \varphi \text{ and } \exists \sigma<\tau\ \sigma\vDash\varphi$$ is equal to the number of satisfying truth assignments $- 1$. Adding $\varphi$ itself it adds up to the number of satisfying truth assignments for $\varphi$.

There are $2^{|\varphi|}$ truth assignments. Each $\tau$ either satisfies $\varphi$ or $\lnot \varphi$ (and not both). For every formula $\varphi$, consider the $2(2^{|\varphi|}+1)$ strings $\langle\varphi\rangle$, $\langle\lnot \varphi\rangle$, $\langle\varphi, \tau\rangle$, and $\langle \lnot\varphi, \tau\rangle$ for $\tau \in \{0,1\}^{|\varphi|}$. Exactly $2^{|\varphi|}$ of these $2^{|\varphi|+1}+2$ strings are in $L$. This means that the number of strings of length $n$ in $L$ is the number of formulas $\varphi$ of encoded length $n$ multiplied by $2^{|\varphi|}$ which polynomial-time computable.

Answer 2

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$?)