<p>Comment => Answer.</p>

<p>In <a href="http://www.sciencedirect.com/science/article/pii/0012365X76900686" rel="nofollow" title="Hamiltonian circuits in random graphs">this paper</a>, 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.</p>

<hr>

<p>Possible approach to new question</p>

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

<p><strong>Claim</strong>: 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.</p>

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

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

CC BY-SA 3.0
2015-12-01T03:26:35.163Z
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
CC BY-SA 3.0
2015-12-01T07:25:08.363Z
@AndrasFarago I updated my response with a candidate answer to the new question.
Yonatan N
CC BY-SA 3.0
2015-12-01T17:55:31.540Z
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
CC BY-SA 3.0
2015-11-30T17:25:20.120Z
2015-12-01T07:30:00.327Z
2015-12-01T07:30:00.327Z
Yonatan N
<p>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.</p>

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

<p>A good introduction is the article by Brian Hayes <a href="http://www.americanscientist.org/issues/pub/the-easiest-hard-problem" rel="nofollow">"The Easiest Hard Problem"</a> and Cheesman et all's <a href="http://www.dcs.gla.ac.uk/~pat/cpM/papers/cheeseman91where.pdf" rel="nofollow">"Where the <em>Really</em> Hard Problems Are"</a>.  Searching for "NP-Complete phase transitions" should give you plenty of material.</p>

<p>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 <strong>probability</strong> of finding a solution and the <strong>difficulty</strong> 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.</p>

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

CC BY-SA 3.0
2015-12-02T02:44:47.880Z
2015-12-02T02:44:47.880Z
user834
<p>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}$.</p>

CC BY-SA 3.0
2015-11-26T16:24:00.700Z
Could you please provide a link or reference to a paper that contains the proof?
Andras Farago
CC BY-SA 3.0
2015-11-26T16:40:23.587Z
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
CC BY-SA 3.0
2015-11-26T23:36:45.803Z
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
CC BY-SA 3.0
2015-11-27T02:43:18.277Z
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
CC BY-SA 3.0
2015-11-27T04:21:35.263Z
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
CC BY-SA 3.0
2015-11-27T04:57:09.777Z
For example say $n=4$ and we are given $-7$, $3$ and two other numbers between $-8$ and $7$ and we want to find a subset with sum $0$.  In the new problem, $-7$ becomes $11111001_2 = 249$ and $3$ becomes $00000011_2 = 3$, likewise for the other two numbers, and four new numbers are introduced to pad the new problem to the correct size (we can use $00010000_2$, $00010001_2$, $0001010_2$, and $0001011_2$).  So the new problem has a set with eight elements, any solution must be a subset of the first four, it allows any sum divisible by $256$, corresponding to sums of $0$ in the original problem.
Dan Brumleve
CC BY-SA 3.0
2015-11-25T16:08:41.640Z
2015-12-01T00:42:57.550Z
2015-12-01T00:42:57.550Z
Dan Brumleve
<p>(This question is related to a previous one, see the discussion in <a href="https://cstheory.stackexchange.com/questions/33088/almost-easy-np-complete-problems">&quot;Almost easy&quot; NP-complete problems</a>, but it may also be of independent interest, so I post it as a separate question.) </p>

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

<p>It is not hard to construct <em>artificial</em> examples of <strong>NP</strong>-complete problems with high density. For example, let $L$ be <em>any</em> <strong>NP</strong>-complete language. For a binary string $z$, let $w(z)$ denote the <em>weight</em> 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 <strong>NP</strong>-complete.</p>

<p>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 <strong>NP</strong>-complete problems with high density, and I was surprised that this turned out harder than I thought. So, the <strong>question</strong> is:</p>

<blockquote>
  <p>What are some examples of <em>natural</em> <strong>NP</strong>-complete problems with high density?</p>
</blockquote>

<p><strong>Edit:</strong> </p>

<p>From the discussion in the comments I realized that a better question would be this:</p>

<blockquote>
  <p>What are some examples of <em>natural</em> <strong>NP</strong>-complete problems with the property that <strong>both</strong> the yes-instances and the no-instances have high density?</p>
</blockquote>

CC BY-SA 3.0
2015-11-19T19:19:31.750Z
Care to list examples that you found to have low density?
usul
CC BY-SA 3.0
2015-11-19T20:01:15.003Z
Perhaps colorability of planar graphs: given an integer $k$ and a planar graph $G$, is $G$ $k$-colorable ?
Marzio De Biasi
CC BY-SA 3.0
2015-11-19T20:55:52.997Z
@usul Some examples of low density NP-complete problems (low density = less than a constant fraction of $2^n$) : 1.) 3SAT;  2.) given an $n$-vertex graph , does it contain a clique on $cn$ vertices? ($0<c<1$, constant); 3.) Does the graph have a proper vertex coloring  with $k$ colors? ($k\geq 3$, constant). In fact, I did not find any natural NP-complete problem so far for which I could prove it does not have low density.
Andras Farago
CC BY-SA 3.0
2015-11-19T21:13:21.023Z
@MarzioDeBiasi For planar graphs only the case $k=3$ can be a hard decision problem (with $k\leq 2$ it is in P, and with $k\geq 4$ the answer is always yes by the Four Color Theorem). However, only an exponentially small fraction of all planar graphs does not have a $K_4$ subgraph (see http://www.sciencedirect.com/science/article/pii/S0095895604000905). Therefore, all but a vanishing fraction of planar graphs need 4 colors.
Andras Farago
CC BY-SA 3.0
2015-11-19T21:19:23.090Z
@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
CC BY-SA 3.0
2015-11-19T21:35:11.590Z
@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
CC BY-SA 3.0
2015-11-19T21:50:37.943Z
@MarzioDeBiasi Good point! This is indeed NP-complete (because graph 3-colorability can be reduced to planar graph 3-colorability), and, with $k$ included in the input,  it has really high density. The problem can also be viewed natural. Although this is still not really what I was looking for, since it only has high density because a large set of always-yes instances are added, the "real" NP-complete part has low density. In this sense it goes along the same lines as my construction in the question.
Andras Farago
CC BY-SA 3.0
2015-11-20T20:37:05.350Z
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
CC BY-SA 3.0
2015-11-21T01:41:40.237Z
@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
CC BY-SA 3.0
2015-12-01T07:26:15.487Z
Given your 11/19 21:50 comment, maybe you want to consider the density of a complexity core? Or maybe you want an intermediate defn, e.g. that for any subset $L' \subset L$ such that $L' \in \mathsf{P}$, $L \backslash L'$ has high density for infinitely many $n$? (i.o. high density seems to me a much more natural requirement than a.e. high density... for example, a natural encoding of graphs as input only has valid inputs at lengths of the form $\binom{n}{2}$...)
Joshua Grochow
CC BY-SA 3.0
2015-12-01T18:09:34.133Z
@JoshuaGrochow Good point! Is there any known _natural_ NP-complete problem with a dense complexity core? I know that for a P-bi-immune language the complexity core is $\{0,1\}^*$, but I do not know any natural P-bi-immune language in NP.
Andras Farago
CC BY-SA 3.0
2015-12-01T18:23:15.177Z
@AndrasFarago: [Orponen and Schoning](http://dx.doi.org/10.1016/S0019-9958(86)80024-9) 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
<cc.complexity-theory><ds.algorithms><complexity-classes><np>
Natural NP-complete problems with high density?
Andras Farago
# Natural NP-complete problems with high density?

(Asked by: username_0 on 2015-11-19)

(This question is related to a previous one, see the discussion in ["Almost easy" NP-complete problems](https://cstheory.stackexchange.com/questions/33088/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?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, np

> **Comments:**
> **username_1**: Care to list examples that you found to have low density?  
> **username_2**: Perhaps colorability of planar graphs: given an integer $k$ and a planar graph $G$, is $G$ $k$-colorable ?  
> **username_0**: @username_1 Some examples of low density NP-complete problems (low density = less than a constant fraction of $2^n$) : 1.) 3SAT;  2.) given an $n$-vertex graph , does it contain a clique on $cn$ vertices? ($0<c<1$, constant); 3.) Does the graph have a proper vertex coloring  with $k$ colors? ($k\geq 3$, constant). In fact, I did not find any natural NP-complete problem so far for which I could prove it does not have low density.  
> **username_0**: @MarzioDeBiasi For planar graphs only the case $k=3$ can be a hard decision problem (with $k\leq 2$ it is in P, and with $k\geq 4$ the answer is always yes by the Four Color Theorem). However, only an exponentially small fraction of all planar graphs does not have a $K_4$ subgraph (see http://www.sciencedirect.com/science/article/pii/S0095895604000905). Therefore, all but a vanishing fraction of planar graphs need 4 colors.  
> **username_2**: @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.  
> **username_2**: @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 :-)  
> **username_0**: @MarzioDeBiasi Good point! This is indeed NP-complete (because graph 3-colorability can be reduced to planar graph 3-colorability), and, with $k$ included in the input,  it has really high density. The problem can also be viewed natural. Although this is still not really what I was looking for, since it only has high density because a large set of always-yes instances are added, the "real" NP-complete part has low density. In this sense it goes along the same lines as my construction in the question.  
> **username_3**: 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).  
> **username_0**: @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.  
> **username_4**: Given your 11/19 21:50 comment, maybe you want to consider the density of a complexity core? Or maybe you want an intermediate defn, e.g. that for any subset $L' \subset L$ such that $L' \in \mathsf{P}$, $L \backslash L'$ has high density for infinitely many $n$? (i.o. high density seems to me a much more natural requirement than a.e. high density... for example, a natural encoding of graphs as input only has valid inputs at lengths of the form $\binom{n}{2}$...)  
> **username_0**: @JoshuaGrochow Good point! Is there any known _natural_ NP-complete problem with a dense complexity core? I know that for a P-bi-immune language the complexity core is $\{0,1\}^*$, but I do not know any natural P-bi-immune language in NP.  
> **username_4**: @AndrasFarago: [Orponen and Schoning](http://dx.doi.org/10.1016/S0019-9958(86)80024-9) 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.  

---

## 3 answers

### Answer by username_3 on 2015-11-30. Score: 8

Comment => Answer.

In [this paper](http://www.sciencedirect.com/science/article/pii/0012365X76900686 "Hamiltonian circuits in random graphs"), 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.

> **Comments:**
> **username_0**: 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!  
> **username_3**: @AndrasFarago I updated my response with a candidate answer to the new question.  
> **username_0**: 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.  

---

### Answer by username_5 on 2015-12-02. Score: 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"](http://www.americanscientist.org/issues/pub/the-easiest-hard-problem) and Cheesman et all's ["Where the *Really* Hard Problems Are"](http://www.dcs.gla.ac.uk/~pat/cpM/papers/cheeseman91where.pdf). 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.


---

### Answer by username_6 on 2015-11-25. Score: 3

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

> **Comments:**
> **username_0**: Could you please provide a link or reference to a paper that contains the proof?  
> **username_6**: 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.  
> **username_0**: 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.  
> **username_6**: 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}$.  
> **username_0**: 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.  
> **username_6**: For example say $n=4$ and we are given $-7$, $3$ and two other numbers between $-8$ and $7$ and we want to find a subset with sum $0$.  In the new problem, $-7$ becomes $11111001_2 = 249$ and $3$ becomes $00000011_2 = 3$, likewise for the other two numbers, and four new numbers are introduced to pad the new problem to the correct size (we can use $00010000_2$, $00010001_2$, $0001010_2$, and $0001011_2$).  So the new problem has a set with eight elements, any solution must be a subset of the first four, it allows any sum divisible by $256$, corresponding to sums of $0$ in the original problem.  

---

