# Natural NP-complete problems with high density?

(This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.)

Let us say that a language $L\subseteq \{0,1\}^*$ has high density, if it contains a positive constant fraction of all $n$-bit strings. That is, there is a constant $c>0$, such that $$|L\cap \{0,1\}^n|\geq c2^n$$ holds for all $n$.

It is not hard to construct artificial examples of NP-complete problems with high density. For example, let $L$ be any NP-complete language. For a binary string $z$, let $w(z)$ denote the weight of $z$, which is the number of 1-bits in $z$. Now define $$L'=\{xx\,|\,x\in L\}\cup \{y\,|\, w(y)\:\mbox{is odd}\}.$$ It is easy to see that $L'$ has high density, and it still remains NP-complete.

The above example, however, is quite artificial, it is constructed for the sole reason of exhibiting this property. I expected that one could easily find natural NP-complete problems with high density, and I was surprised that this turned out harder than I thought. So, the question is:

What are some examples of natural NP-complete problems with high density?

Edit:

From the discussion in the comments I realized that a better question would be this:

What are some examples of natural NP-complete problems with the property that both the yes-instances and the no-instances have high density?

• @AndrasFarago: indeed I included $k$ in the input (a quite natural condition); so, for $k \geq 4$ we know that the answer is yes ... and this should be enough for an exponential number of yes "natural" instances. – Marzio De Biasi Nov 19 '15 at 21:19
• @AndrasFarago: The (natural?) problem "Given a planar graph $G$ and an integer $k \geq 1$, is $G$ k-colorable?" IS NP-complete. Perhaps it is not so natural, but it is NP-complete and has a lot of yes instances :-) – Marzio De Biasi Nov 19 '15 at 21:35
• The details depend on the encoding, but a result of Posa states that there exists a k for which G(n,(k log n)/n) graphs contain Hamiltonian circuits with probability 1 (as n goes to infinity). – Yonatan N Nov 20 '15 at 20:37
• @YonatanN Yes, this looks a great example! Hamiltonian circuit is a natural NP-complete problem, and the cited result implies that the overwhelming majority of graphs do have a Hamiltonian circuit. Therefore, the language indeed has high density, without any "hacking" to achieve it. I recommend posting it as an answer, with some more details. I guess, probably a good number of other examples can be found along these lines, using results about random graphs. – Andras Farago Nov 21 '15 at 1:41
• @AndrasFarago: Orponen and Schoning showed that NP-complete problems have polynomially non-sparse complexity cores (assuming $P \neq NP$), and EXP-complete problems have exponentially dense complexity cores. That's the best I know of. – Joshua Grochow Dec 1 '15 at 18:23

In this paper, Posa shows that for some constant $c$, a graph chosen from the Erdos-Renyi random graph distribution $G(n, c \log n / n)$ has a Hamiltonian cycle with probability approaching $1$ as $n \rightarrow \infty$. If we encode the input to the Hamiltonian Cycle problem as simply a bit-string representing its adjacency matrix, the uniform distribution over $n$-vertex inputs would be exactly the $G(n,1/2)$ distribution (with some irrelevant self loops) -- much more dense than what's needed. Since the existence of a Hamiltonian cycle is a monotone property, the conclusion that the vast majority of graphs have a Hamiltonian cycle follows.

Possible approach to new question

My guess is that you get exactly that for the question of "does there exist a Hamiltonian cycle where $u$ is a neighbor of $v$". I'm not going to fully justify everything, but the reasoning may go roughly as follows.

Claim: For $G \sim G(n,1/2)$ and $u$ and $v$ designated uniformly at random, there is a Hamiltonian path starting at $v$ and ending at $u$ with at least some constant probability.

Take a random Hamiltonian cycle (many of which will exist with overwhelming probability in $G(n,p)$). We show how to transform this, with at least constant probability of success, into a Hamiltonian Path with endpoints $u$ and $v$. For simplicity, we ignore (immediately fail on) the $o(1)$ fraction of cases in which $u$ and $v$ are a distance less than $4$ apart (thus, their neighborhoods are disjoint and not adjacent in the cycle). An intuitive guess is that the two neighbors of $v$ in this cycle should have an edge with constant probability (close to $1/2$), as should $v$ to one or both of the neighbors of $u$ (probability close to $3/4$). If all this happens (probability close to $3/8$), there is a Hamiltonian Path starting at $v$, heading to a neighbor of $u$, continuing along the original Hamiltonian path in the direction away from $u$ (skipping over $v$ once we get to that point), and finally ending at $u$. $\square$

Thus, with some constant probability $c$, there should be a Hamiltonian path starting at $v$ and ending at $u$. The chance that they're adjacent is $1/2$, so with probability $c/2 = \Omega(1)$, there is a Hamiltonian cycle in which $u$ is a neighbor of $v$. Conversely, with probability at least $1/2$ the vertices $u$ and $v$ are not adjacent, so there can't possibly be a Hamiltonian cycle with $u$ and $v$ as neighbors. The conclusion follows.

• This is a great answer to the original question! The modified question asks for an example where both the yes- and no-instances have high density. This could be achieved by requiring that the graph has Hamiltonian cycle and it has at most $n(n-1)/4$ edges. Then half of all graphs will be no-instances, and still nearly half of graphs remain yes-instances. However, it is debatable whether this modified problem is still natural, or it is just a "hacked version" to satisfy a requirement. It would be nice to see a generically natural example with two-sided high density! – Andras Farago Dec 1 '15 at 3:26
• @AndrasFarago I updated my response with a candidate answer to the new question. – Yonatan N Dec 1 '15 at 7:25
• The modified answer looks indeed good: given a graph, and vertices $u,v$ in it, is there a Hamiltonian cycle on which $u,v$ are neighbors? For half of all graphs the answer is immediately no, as they do not contain the edge $(u,v)$. For most of the other half the answer is yes, according to the random graphs based argument. Interestingly, however, the algorithmic solution is still trivial on all but a vanishing set of inputs: always say "yes" if the edge $(u,v)$ is in the graph, and say "no" otherwise. This will err only on a vanishing subset of all graphs. – Andras Farago Dec 1 '15 at 17:55

Given $n$ non-negative integers less than $2^n$, encoded as $n^2$ input bits (and with a non-square number of input bits decoded by first padding with zeroes to reach the next square length), is there a non-empty subset whose sum is divisible by $2^n$? This is a variation of SUBSET-SUM and has limit density $1-\frac{1}{e}$.

• Could you please provide a link or reference to a paper that contains the proof? – Andras Farago Nov 26 '15 at 16:24
• It's my own idea, I'm not sure if I can prove it. The reason I think it is true is that a subset of a random instance has a $\frac{1}{2^n}$ chance of being a solution, and we have $2^n$ subsets, so the probability of there not being a solution is $(1-\frac{1}{2^n})^{2^n}$ which is $\frac{1}{e}$ in the limit. – Dan Brumleve Nov 26 '15 at 16:40
• Unfortunately, the argument is not clear enough (for me). For example, the different subsets are not independent, as they may overlap. Also, the NP-completeness does not seem to directly follow from the NP-completeness of SUBSET SUM. – Andras Farago Nov 26 '15 at 23:36
• To reduce from SUBSET-SUM given $n$ integers between $-2^{n-1}$ and $2^{n-1}-1$ and a target of $0$, which is well-known to be NP-complete, encode the $n$ numbers as $2 \cdot n$-bit strings in two's complement format, choose $n$ other integers between $0$ and $2^{2n}-1$ which cannot possibly be part of a null sum (for example by setting one of the bits in the upper half and some of the lower bits), and ask whether any subset of these $2 \cdot n$-bit strings (interpreted as the encoding of an integer between $0$ and $2^{2 \cdot n}-1$) sums to a multiple of $2 ^ {2 \cdot n}$. – Dan Brumleve Nov 27 '15 at 2:43
• It seems that this reduction has only one-sided correctness. If the answer to the divisibility question is yes, then the original SUBSET-SUM indeed must have a solution. However, if the answer is no, then nothing seems to force the original SUBSET-SUM to also have a no answer, it could still have a solution. That is, some yes-instances of SUBSET-SUM may be mapped to no-instances of the new problem. – Andras Farago Nov 27 '15 at 4:21

If I've understood your question correctly, this relates closely to phase transitions of NP-Complete problems and determining where the transition point is. If you're not familiar, the idea is to take an ensemble of NP-Complete instances and choose random instances based on a parameter. Tuning that parameter will land you in the 'easy', 'hard' or 'middle' region, where 'easy' means the probability of solution is almost surely 1, 'hard' means the probability of a solution is almost surely 0 and the transition point is somewhere in the middle.

For example, choosing the ensemble of Erdos-Renyi random graphs with the average degree as a parameter for the Hamiltonian path problem. Low degree leads to almost surely no Hamiltonian cycles whereas high degree yields a Hamiltonian cycle almost surely. When increasing the average degree (somewhere around 2, say), there is a rapid transition, the so called phase transition, from almost surely no solution existing to a cycle almost surely being present.

A good introduction is the article by Brian Hayes "The Easiest Hard Problem" and Cheesman et all's "Where the Really Hard Problems Are". Searching for "NP-Complete phase transitions" should give you plenty of material.

The common folklore is that "hard" problems, that is, problems that are difficult to solve, happen right in the middle of the transition point, where you'd expect maybe something like probability $\frac{1}{2}$ of finding a solution. This intuition turns out to be wrong and there should be a distinction between the probability of finding a solution and the difficulty of finding a solution. For example, for Hamiltonian cycles in Erdos-Renyi random graphs, there's provably almost sure polynomial times to determine whether a graph is Hamiltonian or not, even precisely in the middle of the transition point. This doesn't mean random graphs are easy, it just means that a particular distribution (the Erdos-Renyi distribution for random graphs, say) is easy and that another should be chosen (maybe on graphs whose vertex degrees are power law degree distributed, say) if intrinsically difficult instances are desired.

To me, choosing random instances of NP-Complete problems is "natural" in the sense you use above. I think it's accepted at this point that all NP-Complete problems have a phase transition (on some "natural" parametrization of an ensemble). Once you have an ensemble to choose from and you believe a phase transitions exists, you can tune the parameter to wherever on the curve you like to find the desired proportion of solvable instances you want.