<p>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.]</p>

<p>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.</p>

<p>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...</p>

<p>The objection can also be gotten around by simply <em>not</em> 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.</p>

<p>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).</p>

<p>(Related question: is there an oracle relative to which there is no such $L$?)</p>

CC BY-SA 3.0
2016-11-26T07:13:06.397Z
2016-11-26T07:13:06.397Z
Joshua Grochow
<p>I asked this question a few years ago and Boaz Barak positively <a href="http://blog.computationalcomplexity.org/2003/09/balanced-np-sets.html?m=0" rel="nofollow noreferrer">answered it</a>.</p>

<hr>

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

<p>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.</p>

<p>Let $\langle\ \rangle$ be an encoding that </p>

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

<p>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 \}$$</p>

<p>It is easy to see that $L$ is NP-complete.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2016-11-26T22:56:07.297Z
Even if this is the desired solution, this is a distinctly link-only answer.
user2943160
CC BY-SA 3.0
2016-12-04T12:05:27.370Z
to be clear, there is nothing special about SAT, this would work with any verifier predicate for a NP-complete problem.
Kaveh
CC BY-SA 3.0
2016-12-06T01:54:50.547Z
@Kaveh, don't you use here a particular property of SAT, that the instances come in pairs $\phi$, $\lnot \phi$ such that any given witness $\tau$ is a witness for exactly one of the two in the pair?  How would you do that for, e.g. 3-COLOR?
Neal Young
CC BY-SA 3.0
2016-12-06T09:29:08.237Z
@Neal, let V(x,y) be a verifier for an NP-complete problem. Consider W(x,b,y) := V(x,y)=b. It is still NP-complete and each y is a witness either for x,0 or x,1. Not as nice as SAT though.
Kaveh
CC BY-SA 3.0
2016-12-07T13:20:34.747Z
@Kaveh, e.g. with SAT are you suggesting $$A = \{(\phi, b, \tau) : (\tau \mbox{ satisfies } \phi) \leftrightarrow b=1\}?$$  But that is in P, and if you try to fix that by taking the union with, say, $B = \{(\phi, b) : \tau \in SAT \leftrightarrow b = 1\}$, the union $A\cup B$ is both NP-hard and co-NP-hard (so likely not in NP). EDIT: Oh, I see, you mean to take the union of $A$ with, say, $C=\{(\phi, b) : \exists \tau.~[(\tau \mbox{ satisfies } \phi) \leftrightarrow b=1]\}$...
Neal Young
CC BY-SA 3.0
2016-12-12T10:59:20.200Z
Yes, $\{(x,b) \mid \exists y W(x,b,y)\} \cup \{(x,b,y) \mid W(x,b,y) \text{ and $y$ is not the first witness}\}$
Kaveh
CC BY-SA 3.0
2016-11-26T12:24:44.587Z
2016-11-29T04:42:55.140Z
2016-11-29T04:42:55.140Z
Ryan O'Donnell
<p>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 <em>precisely</em> half of all $n$-bit instances.</p>

CC BY-SA 3.0
2016-11-25T16:20:42.307Z
Would be very surprising if there isn't but thinking about it for a few minutes couldn't find a construction.
Kaveh
CC BY-SA 3.0
2016-11-25T18:55:36.393Z
FWIW there is such an $L$ that is NP-hard and in NP/POLY...
Neal Young
CC BY-SA 3.0
2016-11-26T02:15:01.887Z
For a bijective binary encoding $e$ of CNF formulas, $\{e(\varphi)1\ |\ \varphi$ satisfiable $\} \cup \{e(\varphi)0\ |\ \varphi$ unsatisfiable $\}$ should work.
Klaus Draeger
CC BY-SA 3.0
2016-11-26T04:43:12.040Z
@KlausDraeger Unsatisfiability is not an NP property, unless NP=co-NP.
Andras Farago
CC BY-SA 3.0
2016-11-26T06:59:09.980Z
Is there any oracle $O$ such that there does not exist $\mathcal{L}\in {\bf NP-Complete}^O$ with this property?
Erfan Khaniki
CC BY-SA 3.0
2016-11-26T15:18:07.860Z
It's easy to come up with an NP-hard language with that property. But I am not sure if that helps towards finding an NP-complete language. The NP-hard language can be obtained by first picking any NP-hard language $L_0$ and then constructing the language where for every string $x$ you take the string $1 || x$ if $x \in L_0$ and $0 || x$ otherwise.
kasperd
<cc.complexity-theory><np><np-complete>
Is there an NP-complete language that contains precisely half of the n-bit instances?
Andras Farago
# Is there an NP-complete language that contains precisely half of the n-bit instances?

(Asked by: username_0 on 2016-11-25)

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.

**Tags:** cc.complexity-theory, np, np-complete
> **Comments:**
> **username_1**: Would be very surprising if there isn't but thinking about it for a few minutes couldn't find a construction.  
> **username_2**: FWIW there is such an $L$ that is NP-hard and in NP/POLY...  
> **username_3**: For a bijective binary encoding $e$ of CNF formulas, $\{e(\varphi)1\ |\ \varphi$ satisfiable $\} \cup \{e(\varphi)0\ |\ \varphi$ unsatisfiable $\}$ should work.  
> **username_0**: @KlausDraeger Unsatisfiability is not an NP property, unless NP=co-NP.  
> **username_4**: Is there any oracle $O$ such that there does not exist $\mathcal{L}\in {\bf NP-Complete}^O$ with this property?  
> **username_5**: It's easy to come up with an NP-hard language with that property. But I am not sure if that helps towards finding an NP-complete language. The NP-hard language can be obtained by first picking any NP-hard language $L_0$ and then constructing the language where for every string $x$ you take the string $1 || x$ if $x \in L_0$ and $0 || x$ otherwise.  

---

## 2 answers

### Answer by username_7 on 2016-11-26. Score: 24 | Accepted answer

I asked this question a few years ago and Boaz Barak positively [answered it](http://blog.computationalcomplexity.org/2003/09/balanced-np-sets.html?m=0).

---

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.

> **Comments:**
> **username_8**: Even if this is the desired solution, this is a distinctly link-only answer.  
> **username_1**: to be clear, there is nothing special about SAT, this would work with any verifier predicate for a NP-complete problem.  
> **username_2**: @Kaveh, don't you use here a particular property of SAT, that the instances come in pairs $\phi$, $\lnot \phi$ such that any given witness $\tau$ is a witness for exactly one of the two in the pair?  How would you do that for, e.g. 3-COLOR?  
> **username_1**: @Neal, let V(x,y) be a verifier for an NP-complete problem. Consider W(x,b,y) := V(x,y)=b. It is still NP-complete and each y is a witness either for x,0 or x,1. Not as nice as SAT though.  
> **username_2**: @Kaveh, e.g. with SAT are you suggesting $$A = \{(\phi, b, \tau) : (\tau \mbox{ satisfies } \phi) \leftrightarrow b=1\}?$$  But that is in P, and if you try to fix that by taking the union with, say, $B = \{(\phi, b) : \tau \in SAT \leftrightarrow b = 1\}$, the union $A\cup B$ is both NP-hard and co-NP-hard (so likely not in NP). EDIT: Oh, I see, you mean to take the union of $A$ with, say, $C=\{(\phi, b) : \exists \tau.~[(\tau \mbox{ satisfies } \phi) \leftrightarrow b=1]\}$...  
> **username_1**: Yes, $\{(x,b) \mid \exists y W(x,b,y)\} \cup \{(x,b,y) \mid W(x,b,y) \text{ and $y$ is not the first witness}\}$  

---

### Answer by username_6 on 2016-11-26. Score: 8

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


---

