26
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Would be very surprising if there isn't but thinking about it for a few minutes couldn't find a construction. $\endgroup$ – Kaveh Nov 25 '16 at 16:20
  • 2
    $\begingroup$ FWIW there is such an $L$ that is NP-hard and in NP/POLY... $\endgroup$ – Neal Young Nov 25 '16 at 18:55
  • $\begingroup$ For a bijective binary encoding $e$ of CNF formulas, $\{e(\varphi)1\ |\ \varphi$ satisfiable $\} \cup \{e(\varphi)0\ |\ \varphi$ unsatisfiable $\}$ should work. $\endgroup$ – Klaus Draeger Nov 26 '16 at 2:15
  • 4
    $\begingroup$ @KlausDraeger Unsatisfiability is not an NP property, unless NP=co-NP. $\endgroup$ – Andras Farago Nov 26 '16 at 4:43
  • $\begingroup$ Is there any oracle $O$ such that there does not exist $\mathcal{L}\in {\bf NP-Complete}^O$ with this property? $\endgroup$ – Erfan Khaniki Nov 26 '16 at 6:59
25
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ Even if this is the desired solution, this is a distinctly link-only answer. $\endgroup$ – user2943160 Nov 26 '16 at 22:56
  • $\begingroup$ to be clear, there is nothing special about SAT, this would work with any verifier predicate for a NP-complete problem. $\endgroup$ – Kaveh Dec 4 '16 at 12:05
  • $\begingroup$ @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? $\endgroup$ – Neal Young Dec 6 '16 at 1:54
  • $\begingroup$ @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. $\endgroup$ – Kaveh Dec 6 '16 at 9:29
  • $\begingroup$ @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]\}$... $\endgroup$ – Neal Young Dec 7 '16 at 13:20
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.