Natural NP-complete problems with high density?

Question

(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?

Answer 1

Comment => Answer.

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.

Answer 2

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}$.

Answer 3

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.