Is there an NP-complete language that contains precisely half of the n-bit instances? 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.
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&lt;\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&lt;\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.