<p>INDEPENDENT SET is NP-complete for <a href="http://graphclasses.org/classes/gc_633.html" rel="nofollow noreferrer">(cross,triangle)-free graphs</a>, but can be solved in linear time for <a href="http://graphclasses.org/classes/gc_632.html" rel="nofollow noreferrer">(chair,triangle)-free graphs</a>.  (The X-free graphs are those that contain no graph from X as an induced subgraph.)</p>

<p>chair: <img src="https://i.sstatic.net/HXHk2.gif" alt="image of chair graph from ISGCI">
 triangle: <img src="https://i.sstatic.net/xJWEO.gif" alt="image of triangle graph from ISGCI">
 cross: <img src="https://i.sstatic.net/wRXrg.gif" alt="image of cross graph from ISGCI"></p>

<p>Notice that the cross is obtained from the chair by adding a single edge.</p>



CC BY-SA 3.0
2013-04-29T19:23:53.070Z
What about this more simple example: INDEPENDENT SET is NP-c for $K_{1,4}$-free graphs, but can be solved in linear time for $K_{1,3}$-free (i.e., claw-free) graphs.
vb le
CC BY-SA 4.0
2010-10-26T17:38:17.857Z
2018-12-27T16:00:26.783Z
2018-12-27T16:00:26.783Z
András Salamon
<p>I am not sure I would go along with your characterization that adding a single edge to the input makes the problem NP-complete, since one is actually allowing an edge to be added to every one of the infinitely many input instances.</p>

<p>Here is an example of a problem which shows a sharp dichotomy along the lines you suggest.</p>

<p>The problem of determining whether there is a graph homomorphism from the input graph G to a fixed template graph H is in P when H is a graph with a self-loop or is a bipartite loopless graph.  When H is not bipartite (this can often be achieved by adding a single edge) then the problem becomes NP-complete.</p>

<ul>
<li>P. Hell and J. Nešetřil, <em>Complexity of H-colouring</em>, J. Comb. Th. B <strong>48</strong> 92–110, 1990. doi: <a href="http://dx.doi.org/10.1016/0095-8956%2890%2990132-J">10.1016/0095-8956(90)90132-J</a></li>
</ul>

<p>The key here is that 2-colouring is in P (this corresponds to a homomorphism to $P_3$, the path on 3 vertices), while 3-colouring is NP-complete (this corresponds to a homomorphism to $K_3$, the triangle).</p>

CC BY-SA 2.5
2010-10-24T22:18:48.317Z
2010-10-24T22:18:48.317Z
András Salamon
<p>This answers the question asked in the question-title, but not the one asked in the question.</p>

<p>A shocking example of jump-in-hardness arises from the question, "How many satisfying assignments does a planar formula have, modulo $n$?"  This was widely thought to be #P-hard, and it is for "most" values of $n$, but if $n$ is a Mersenne integer (for example $n=7$, because 7 is of form $2^3-1$), then the answer can be computed in polynomial time.</p>

<p>This was first discovered by Valiant, in his groundbreaking Holographic Algorithms paper.</p>

CC BY-SA 3.0
2013-12-13T04:25:37.190Z
That is not quite right. The formula doesn't just need to be planar. It also needs to be monotone, read-twice, and have size $k$ clauses, where $n = 2^k - 1$. Valiant's presentation in Holographic Algorithms is to fix clause size to $k=3$ and then vary the modulus. Characteristic 0 hardness (i.e. #P-harness) was known. Valiant proved hardness mod 2 and tractable mod 7. Note that this hardness is $\oplus P = \#_2 P$ hardness, not #P-hardness. I believe the complexity mod other values is open. Later, Jin-Yi Cai and Pinyan Lu gave tractability for all $k$.
Tyson Williams
CC BY-SA 3.0
2013-12-13T04:27:05.603Z
For more on this, including the paper references, see [Holographic_algorithm#History](https://en.wikipedia.org/wiki/Holographic_algorithm#History) on Wikipedia.
Tyson Williams
CC BY-SA 2.5
2010-10-25T17:11:01.197Z
2010-10-25T17:11:01.197Z
Aaron Sterling
<p>Here's another interesting example, raised in induced subgraph detection:</p>

<p>A <strong>theta</strong> is a graph with non-adjacent vertices <span class="math-container">$x,y$</span>, three paths <span class="math-container">$P_1, P_2, P_3$</span> from <span class="math-container">$x$</span> to <span class="math-container">$y$</span>, where any two paths induced a cycle with length greater than 3.</p>

<p>A <strong>pyramid</strong> is a graph with a vertex <span class="math-container">$x$</span>, a triangle <span class="math-container">$y_1,y_2,y_3$</span>, and paths <span class="math-container">$P_i$</span> from <span class="math-container">$x$</span> to <span class="math-container">$y_i$</span> for each <span class="math-container">$i=1,2,3$</span>, with at most one path with length one.</p>

<p>Finally, a <strong>prism</strong> is a graph with two triangle <span class="math-container">$x_1,x_2,x_3$</span> and <span class="math-container">$y_1,y_2,y_3$</span>, and paths <span class="math-container">$P_i$</span> from <span class="math-container">$x_i$</span> to <span class="math-container">$y_i$</span> for each <span class="math-container">$i=1,2,3$</span>. </p>

<p>It is easy to describe in figures:</p>

<p><img src="https://i.sstatic.net/XMBzg.jpg" alt="theta, prism and pyramid"></p>

<p>For detecting induced theta and pyramid, it is known to be in polynomial time. (In fact, the best known algorithm for theta takes <span class="math-container">$O(n^{11})$</span> time, and for pyramid it takes <span class="math-container">$O(n^9)$</span>.) But for detecting an induced prism, the problem becomes NP-hard.</p>

<p>One can see "<a href="https://arxiv.org/abs/1309.0971" rel="nofollow noreferrer">Detecting induced subgraphs</a>" by Leveque, Lin, Maffray and Trotignon for reference. The reason that theta and pyramid are relatively easy is related to the "three-in-a-tree" problem, described in "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.7221&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">The three-in-a-tree problem</a>" by Chudnovsky and Seymour.</p>

CC BY-SA 4.0
2010-11-06T15:34:09.147Z
2018-12-27T23:17:16.887Z
2018-12-27T23:17:16.887Z
Hsien-Chih Chang 張顯之
<p>I think that it does not make much sense to talk about instances. We can talk about two distribution of input instances with different difficulties, but it would be more interesting if there is relation between the distribution, or between instances in the distributions. </p>

<p>We can consider a parameterized family of distributions, and then talk about what happens when we change the parameter. You might be interested in what is called the <em>threshold phenomenon</em>, "where a system undergoes a swift qualitative change as a result of a small change in a parameter ...". Take a look at this survey: <a href="http://www.ma.huji.ac.il/~ehudf/">Ehud Friedgut</a>, "<a href="http://www.ma.huji.ac.il/~ehudf/docs/survey.ps">Hunting for Sharp Thresholds</a>", Random Structures Algorithms 26, 2005.</p>

<p>I think one of the most striking and beautiful examples is the random k-SAT with clause density $\Delta$, the phase transition is really amazing.</p>

CC BY-SA 2.5
2010-10-24T23:25:41.720Z
2010-10-24T23:25:41.720Z
Kaveh
<p>er ... i'm sure you're looking for less trivial examples... but I would like to point out that there's something special about the number $2$ vs $3$. $2-SAT$ to $3-SAT$, $2-COL$ vs $3-COL$, etc. Intuitively, I've always figured it was because a node with at most 2 edges can form at most a line, but a node with 3 edges can form a tree, when we move from 2-3 we get a combinatorial explosion. </p>

CC BY-SA 2.5
2010-10-25T07:43:11.490Z
on the other hand, MAX 2SAT is hard. so 2 isn't THAT special.
Suresh Venkat
CC BY-SA 2.5
2010-11-05T15:36:22.000Z
2 AND perfect completeness seem special though. :)
Daniel Apon
CC BY-SA 2.5
2010-11-05T19:57:47.663Z
Also, 2D perfect matching vs 3D perfect matching.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-24T21:32:49.123Z
2010-10-24T21:32:49.123Z
gabgoh
<p>Inferring types for lambda terms is DEXPTIME-complete with <a href="http://www.springerlink.com/index/7jhk84120120w4xr.pdf">prenex</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.7215&amp;rep=rep1&amp;type=pdf">rank-2</a> polymorphic type systems (when type quantifiers are nested at most one level deep), but becomes <a href="http://www.springerlink.com/index/m0m87453917r5g12.pdf">undecidable</a> for rank-3 and higher. Strange that one extra nesting level can render a problem undecidable. </p>

CC BY-SA 2.5
2010-11-05T06:13:06.423Z
2010-11-05T06:19:59.003Z
2010-11-05T06:19:59.003Z
Alex Rubinsteyn
<p>Finding ground state of planar Ising model with 0 magnetic field is in P, with non-zero magnetic field it is NP-hard. Partition function of planar Ising model with 0 magnetic field is in P, with non-zero magnetic field it is NP-hard.</p>

CC BY-SA 2.5
2010-11-05T07:10:30.553Z
2010-11-05T07:10:30.553Z
Yaroslav Bulatov
<p>Here is a nice problem with an interesting complexity jump like Minimum Bandwidth you 
addressed in your question.</p>

<p>Let $G$ be a graph and $T$ a spanning tree of $G$. The detour for an edge
$uv\in E(G)$ is the unique $u$-$v$ path in $T$. The congestion of $e \in E(T)$,
denoted by $\mathrm{cng}_{G,T}(e)$ is the number of detours that contain $e$. 
The congestion of $G$ in $T$, denoted by $\mathrm{cng}_G(T)$, is the maximum 
congestion over all edges in $T$. The spanning tree congestion of $G$, denoted by 
$\mathrm{stc}(G)$, is the minimum congestion over all spanning trees of $G$. 
The Spanning Tree Congestion problem asks whether a given graph has spanning tree 
congestion at most some given $k$.</p>

<p>The following complexity jump is shown in: <a href="http://link.springer.com/article/10.1007%2Fs00453-011-9565-7">Bodlaender et al., 
<em>Parameterized Complexity of the Spanning Tree Congestion Problem</em>, 
Algorithmica 64 (2012) 85–111</a>: </p>

<p>For every fixed $k$ and $d$ the problem is solvable in linear time for graphs of degree at 
most $d$. In contrast, if we allow <strong>only one</strong> vertex of unbounded degree, the problem immediately 
becomes $\mathsf{NP}$-complete for any fixed $k\ge 8$.</p>

CC BY-SA 3.0
2013-04-29T15:13:49.270Z
2013-04-29T15:13:49.270Z
vb le
<p>I wonder why nobody mentioned this:</p>

<p>Horn-Sat vs K-Sat</p>

<p>I guess everybody knows what it is. If not:</p>

<p>Horn-Sat is to find if a set of horn clauses is satisfiable (each clause has at most 1 positive literal).</p>

<p>K-Sat is to find if a set of clauses is satisfiable (each clause can have more than 1 positive literals).</p>

<p>So allowing more than one positive literal in each clause makes the problem from P-complete NP-complete.</p>

CC BY-SA 2.5
2010-11-06T23:43:13.927Z
2010-11-06T23:43:13.927Z
George
<p>Graph Coloring</p>

<p>As mentioned in another answer, 2-COL is solvable in polynomial time while 3-COL is NP-complete.
But when increasing the number of colors, after some (unknown?) point the problem gets easier!</p>

<p>For example, if we have N vertices and N colors, the problem can be solved by assigning a different color to each vertex.</p>

CC BY-SA 2.5
2010-12-09T23:41:35.370Z
ANY planar graph is 4-colorable.

  [1]: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183538218
rphv
CC BY-SA 2.5
2010-12-09T21:11:33.700Z
2010-12-09T21:11:33.700Z
George
<p>In a similar vein: Permanent vs Determinant.</p>

CC BY-SA 2.5
2010-11-01T02:27:50.850Z
The difference between perm and det is actually much more significant and of a different kind than the other hardness jumps discussed in the question and the other answers. Negation is *very* powerful: in a sense it's what allows us to compute det easily but not perm; Valiant has a paper "Negation can be exponentially powerful" http://portal.acm.org/citation.cfm?id=804412; lots of lower bounds are known for monotone complexity (even in the algebraic model, where monotonicity excludes negations and negative constants), but very few of these translate to non-monotone complexity.
Joshua Grochow
CC BY-SA 2.5
2010-11-01T02:28:51.007Z
Another example: negation is also necessary for Strassen's algorithm for multiplying 2x2 matrices.  Without it you cannot beat the trivial algorithm for multiplying 2x2 matrices.
Joshua Grochow
CC BY-SA 2.5
2010-10-26T09:43:27.640Z
2010-10-26T09:43:27.640Z
Jagadish
<p>I just read a paper that deals with <strong>hypergraph partitioning</strong>. The Problem is defined as this, quote:</p>

<blockquote>
  <p>Given two parameters $k$ and $l$, $1 \leq l &lt; k$, the problem [$P^l_k$] is defined as follows: Let $\mathcal{H} = (V, \mathcal{E})$ be a hypergraph and $t_1, \dots, t_k$ be non-negative integers such that $|V| = n = \sum^k_{i=1} t_i$ and $|\mathcal{E}| = m$. Does there exist a colouring (partition) of $V$ in $k$ subsets of size $t_1, \dots, t_k$ such that the vertices of each hyperedge in $\mathcal{E}$ are coloured with at most $l$ colours?</p>
</blockquote>

<p>In general, it is proven that:</p>

<ul>
<li>$P^1_k$ is solvable in polynomial time (in $n,m$) for fixed $k \geq 2$</li>
<li>$P^l_k$ is NP-complete for all fixed $2 \leq l &lt; k$</li>
</ul>

<p>If this is not "jump" enough, read on. For hypergraphs with disjoint hyperedges, it is shown:</p>

<ul>
<li>$P^1_k$ is NP-complete for all fixed $k \geq 2$</li>
<li>$P^l_k$ is solvable in linear time (in $m$) for fixed $2 \leq l &lt; k$</li>
</ul>

<p>Laurent Lyaudet. 2010. NP-hard and linear variants of hypergraph partitioning. Theor. Comput. Sci. 411, 1 (January 2010), 10-21. <a href="http://dx.doi.org/10.1016/j.tcs.2009.08.035" rel="nofollow noreferrer">http://dx.doi.org/10.1016/j.tcs.2009.08.035</a> </p>

CC BY-SA 3.0
2010-11-10T13:47:36.950Z
2018-04-14T20:42:11.673Z
2018-04-14T20:42:11.673Z
Raphael
<p>Interesting complexity jumps are known for the job shop scheduling problem.</p>
<blockquote>
<p>In the job shop problem we have a set of <span class="math-container">$n$</span> jobs that must be processed on a given set <span class="math-container">$M$</span> of <span class="math-container">$m$</span> machines. Each job <span class="math-container">$j$</span> consists of a chain of <span class="math-container">$\mu_j$</span> operations <span class="math-container">$O_{1j},O_{2j},\dots,O_{\mu_jj}$</span>. Operation <span class="math-container">$O_{ij}$</span> must be processed during <span class="math-container">$p_{ij}$</span> time units without interruption on machine <span class="math-container">$m_{ij}\in M$</span>. A feasible schedule is one in which operation is scheduled only after all its preceding operations have been completed, and each machine processes at most one operation at a time. For any given schedule, let <span class="math-container">$C_j$</span> be the completioon time of the last operation of job <span class="math-container">$j$</span>. Taken <a href="http://scholar.google.com/scholar?hl=en&amp;num=100&amp;q=%22Approximability+of+some+classical+graph+and+scheduling+problems%22&amp;btnG=Search&amp;as_sdt=2001&amp;as_ylo=&amp;as_vis=0" rel="nofollow noreferrer">here</a>.</p>
</blockquote>
<p>There are such objectives as minimizing the makespan <span class="math-container">$C_{max}=max_jC_j$</span> and total completion time <span class="math-container">$\sum C_j$</span>. Regular criteria are defined <a href="http://books.google.com/books?id=MO5dVmXCQWcC&amp;lpg=PA44&amp;ots=-LFmLg0XM-&amp;dq=%22regular%20criteria%22&amp;pg=PA44#v=onepage&amp;q=%22regular%20criteria%22&amp;f=false" rel="nofollow noreferrer">here</a>.</p>
<blockquote>
<p>In the notation of <a href="http://www.math.ucsd.edu/%7Efan/ron/papers/79_03_scheduling_survey.pdf" rel="nofollow noreferrer">Graham et al.</a> this problem is denoted as <span class="math-container">$J||\gamma$</span>, where <span class="math-container">$\gamma$</span> denotes the objective function to be minimized.</p>
<p><span class="math-container">$J2|n=k|F$</span> and <span class="math-container">$J|n=2|F$</span> are polynomially solvable. Here <span class="math-container">$J2$</span> <span class="math-container">$(n=k)$</span> means that the number of machines (jobs) is fixed and equals <span class="math-container">$2$</span> <span class="math-container">$(k)$</span>. <span class="math-container">$F$</span> means an arbitrary regular criterion.</p>
<p><span class="math-container">$J3|n=3|C_{max}$</span>, <span class="math-container">$J3|n=3|\sum C$</span> are weakly NP-hard.</p>
<p><span class="math-container">$J2||C_{max}$</span>, <span class="math-container">$J2||\sum C$</span> are strongly NP-hard.</p>
</blockquote>
<p>Thus, here we can see that there is a jump when we go  from two jobs/machines to three.</p>

CC BY-SA 2.5
2010-12-10T08:58:36.770Z
Good, I'm confused with the special terminology. Could you please simplify the terminology (or even better remove it)?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-10T06:31:09.433Z
2011-01-29T02:55:08.277Z
2020-06-17T09:38:08.363Z
Oleksandr Bondarenko
<p>In many cases, approximating NP-optimization problems give rise to sharp complexity jumps. For example, SET COVER can be approximated within a factor of <span class="math-container">$\ln n$</span> in polynomial time (by the Greedy Algorithm), but it is NP-hard to approximate within a factor of <span class="math-container">$(1-o(1))\ln n$</span>.</p>

CC BY-SA 4.0
2019-01-03T18:34:14.213Z
2019-01-03T18:34:14.213Z
Andras Farago
<p>I think the <a href="https://en.m.wikipedia.org/wiki/Pascal%27s_triangle?wprov=sfla1" rel="nofollow noreferrer">pascal triangle</a> would be it. Each row in the pascal triangle sums to <span class="math-container">$2^n$</span>. The elements are binomial coefficients. So if you find a problem whose performance can be described using binomial coefficients, then simply solving all such problems associated to the n'th row of the pascal triangle already takes <span class="math-container">$2^n$</span>. But note that <span class="math-container">$(a+b)^n=\sum_{i\in{0..n}}{{n}\choose{i}}a^ib^{n-i}$</span> can be represented as a polynomial (of 'a') that has binomial coefficient times powers of 'b' as factors. If 'b' is constant this is a n'th order polynomial <span class="math-container">$p_b(a)$</span>. Setting <span class="math-container">$a=b=1$</span> you get expansion of <span class="math-container">$2^n=p_1(1)$</span> as a sum. Now suppose you have a matrix of problems with performance in two variables proportional to binomial coefficients (compared to problem <em>size</em> described by two variables) arranged like a pascal triangle. Then solving all problems in n'th row must take <span class="math-container">$DTIME(2^n)$</span>. Binomial coefficients describe how many different ways there are to choose k-combinations from n elements. So if your algorithm depends on enumerating k-combinations of n elements  <span class="math-container">$(k&lt;n)$</span> the algorithm cannot be polynomial time. Because if this problem was polynomial time, then above argument proves <span class="math-container">$P=NP=DTIME(2^n)$</span>, since sum of two polynomials is a polynomial. But correct proofs of <span class="math-container">$P=NP$</span> problem either way are rare.</p>

CC BY-SA 4.0
2018-12-31T17:57:44.513Z
2019-01-01T12:29:00.673Z
2019-01-01T12:29:00.673Z
Esa Pulkkinen
<p>One of the more interesting applied examples of hardness jumps can be observed in the following problem:</p>

<p>Consider a soccer league championship with $n$ teams: The problem of deciding whether a given team can (still) win the league is in $P$ if in a match, the winning team is awarded 2 points, the losing one 0 and each team is awarded 1 point in a draw match. But if we change the rules so that the winning team gets 3 points, the same problem becomes $NP$-hard. </p>

<p>The result can be generalized for any $(0, 1, k)$-point rule for every $k > 2$ and even for only three remaining rounds.</p>

<p>Source: “Complexity Theory” by Ingo Wegener (<a href="http://portal.acm.org/citation.cfm?id=1076319">http://portal.acm.org/citation.cfm?id=1076319</a>)</p>

CC BY-SA 2.5
2010-11-05T20:06:01.657Z
this reminds me of TSP: you can get a 1.5 approx with weights that are 1 or 2, but not if weights are 1 or 3
Suresh Venkat
CC BY-SA 2.5
2010-11-05T19:19:39.183Z
2010-11-05T19:19:39.183Z
Dimitri Scheftelowitsch
<p>Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path by growing edge-disjoint paths of length at most $k$ from its nodes ($k$ is called the hair length). Minimum Bandwidth problem is in $P$ for 2-caterpillars but it is $NP$-complete for 3-caterpillars. </p>

<p>Here is a very interesting fact, Minimum bandwidth problem is solvable in polynomial time for 1-caterpillars (hair length at most one) but it is $NP$-complete for cyclic 1-caterpillars (in cyclic caterpillar, one edge is added to connect the endpoints of the main path). So, the addition of exactly one edge makes the problem $NP$-complete.</p>

<blockquote>
  <p>What is the most striking example of problem hardness jump where a small variation of input instance causes a complexity jump from polynomial-time solvability to $NP$-completeness?</p>
</blockquote>

CC BY-SA 3.0
2013-04-29T22:46:08.800Z
Community Wiki?
Niel de Beaudrap
CC BY-SA 2.5
2010-10-26T06:56:15.663Z
Permanent vs Determinant. These are two different problems(so I guess it doesn't qualify as an answer) but the hardness jump is quite striking.
Jagadish
CC BY-SA 2.5
2010-10-26T07:35:46.553Z
@Jagadish, I agree. Still, I think you can post it as answer.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-07T01:31:38.380Z
Permanent of a 0-1 matrix can be seen as the expected value of the determinant of the matrix when the 1 entries are replaced by +1 or -1 at random.
Dana Moshkovitz
CC BY-SA 2.5
2010-12-05T09:01:04.667Z
@Dana, Could you please make your comment a separate answer? (preferably with a reference)
Mohammad Al-Turkistany
<cc.complexity-theory>
Hardness jumps in computational complexity?
Mohammad Al-Turkistany
# Hardness jumps in computational complexity?

(Asked by: username_0 on 2010-10-24)

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path by growing edge-disjoint paths of length at most $k$ from its nodes ($k$ is called the hair length). Minimum Bandwidth problem is in $P$ for 2-caterpillars but it is $NP$-complete for 3-caterpillars.

Here is a very interesting fact, Minimum bandwidth problem is solvable in polynomial time for 1-caterpillars (hair length at most one) but it is $NP$-complete for cyclic 1-caterpillars (in cyclic caterpillar, one edge is added to connect the endpoints of the main path). So, the addition of exactly one edge makes the problem $NP$-complete.

> What is the most striking example of problem hardness jump where a small variation of input instance causes a complexity jump from polynomial-time solvability to $NP$-completeness?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_2**: Permanent vs Determinant. These are two different problems(so I guess it doesn't qualify as an answer) but the hardness jump is quite striking.  
> **username_0**: @Jagadish, I agree. Still, I think you can post it as answer.  
> **username_3**: Permanent of a 0-1 matrix can be seen as the expected value of the determinant of the matrix when the 1 entries are replaced by +1 or -1 at random.  
> **username_0**: @Dana, Could you please make your comment a separate answer? (preferably with a reference)  
> **username_1**: Community Wiki?  

---

## 17 answers

### Answer by username_22 on 2010-11-05. Score: 49 | Accepted answer

One of the more interesting applied examples of hardness jumps can be observed in the following problem:

Consider a soccer league championship with $n$ teams: The problem of deciding whether a given team can (still) win the league is in $P$ if in a match, the winning team is awarded 2 points, the losing one 0 and each team is awarded 1 point in a draw match. But if we change the rules so that the winning team gets 3 points, the same problem becomes $NP$-hard.

The result can be generalized for any $(0, 1, k)$-point rule for every $k > 2$ and even for only three remaining rounds.

Source: “Complexity Theory” by Ingo Wegener (<http://portal.acm.org/citation.cfm?id=1076319>)

> **Comments:**
> **username_11**: this reminds me of TSP: you can get a 1.5 approx with weights that are 1 or 2, but not if weights are 1 or 3  

---

### Answer by username_6 on 2010-10-25. Score: 24

This answers the question asked in the question-title, but not the one asked in the question.

A shocking example of jump-in-hardness arises from the question, "How many satisfying assignments does a planar formula have, modulo $n$?" This was widely thought to be #P-hard, and it is for "most" values of $n$, but if $n$ is a Mersenne integer (for example $n=7$, because 7 is of form $2^3-1$), then the answer can be computed in polynomial time.

This was first discovered by Valiant, in his groundbreaking Holographic Algorithms paper.

> **Comments:**
> **username_7**: That is not quite right. The formula doesn't just need to be planar. It also needs to be monotone, read-twice, and have size $k$ clauses, where $n = 2^k - 1$. Valiant's presentation in Holographic Algorithms is to fix clause size to $k=3$ and then vary the modulus. Characteristic 0 hardness (i.e. #P-harness) was known. Valiant proved hardness mod 2 and tractable mod 7. Note that this hardness is $\oplus P = \#_2 P$ hardness, not #P-hardness. I believe the complexity mod other values is open. Later, Jin-Yi Cai and Pinyan Lu gave tractability for all $k$.  
> **username_7**: For more on this, including the paper references, see [Holographic_algorithm#History](https://en.wikipedia.org/wiki/Holographic_algorithm#History) on Wikipedia.  

---

### Answer by username_4 on 2010-10-26. Score: 21

INDEPENDENT SET is NP-complete for [(cross,triangle)-free graphs](http://graphclasses.org/classes/gc_633.html), but can be solved in linear time for [(chair,triangle)-free graphs](http://graphclasses.org/classes/gc_632.html). (The X-free graphs are those that contain no graph from X as an induced subgraph.)

chair: ![image of chair graph from ISGCI](https://i.sstatic.net/HXHk2.gif)
triangle: ![image of triangle graph from ISGCI](https://i.sstatic.net/xJWEO.gif)
cross: ![image of cross graph from ISGCI](https://i.sstatic.net/wRXrg.gif)

Notice that the cross is obtained from the chair by adding a single edge.

> **Comments:**
> **username_5**: What about this more simple example: INDEPENDENT SET is NP-c for $K_{1,4}$-free graphs, but can be solved in linear time for $K_{1,3}$-free (i.e., claw-free) graphs.  

---

### Answer by username_4 on 2010-10-24. Score: 19

I am not sure I would go along with your characterization that adding a single edge to the input makes the problem NP-complete, since one is actually allowing an edge to be added to every one of the infinitely many input instances.

Here is an example of a problem which shows a sharp dichotomy along the lines you suggest.

The problem of determining whether there is a graph homomorphism from the input graph G to a fixed template graph H is in P when H is a graph with a self-loop or is a bipartite loopless graph. When H is not bipartite (this can often be achieved by adding a single edge) then the problem becomes NP-complete.

* P. Hell and J. Nešetřil, *Complexity of H-colouring*, J. Comb. Th. B **48** 92–110, 1990. doi: [10.1016/0095-8956(90)90132-J](http://dx.doi.org/10.1016/0095-8956%2890%2990132-J)

The key here is that 2-colouring is in P (this corresponds to a homomorphism to $P\_3$, the path on 3 vertices), while 3-colouring is NP-complete (this corresponds to a homomorphism to $K\_3$, the triangle).


---

### Answer by username_8 on 2010-11-06. Score: 14

Here's another interesting example, raised in induced subgraph detection:

A **theta** is a graph with non-adjacent vertices $x,y$, three paths $P\_1, P\_2, P\_3$ from $x$ to $y$, where any two paths induced a cycle with length greater than 3.

A **pyramid** is a graph with a vertex $x$, a triangle $y\_1,y\_2,y\_3$, and paths $P\_i$ from $x$ to $y\_i$ for each $i=1,2,3$, with at most one path with length one.

Finally, a **prism** is a graph with two triangle $x\_1,x\_2,x\_3$ and $y\_1,y\_2,y\_3$, and paths $P\_i$ from $x\_i$ to $y\_i$ for each $i=1,2,3$.

It is easy to describe in figures:

![theta, prism and pyramid](https://i.sstatic.net/XMBzg.jpg)

For detecting induced theta and pyramid, it is known to be in polynomial time. (In fact, the best known algorithm for theta takes $O(n^{11})$ time, and for pyramid it takes $O(n^9)$.) But for detecting an induced prism, the problem becomes NP-hard.

One can see "[Detecting induced subgraphs](https://arxiv.org/abs/1309.0971)" by Leveque, Lin, Maffray and Trotignon for reference. The reason that theta and pyramid are relatively easy is related to the "three-in-a-tree" problem, described in "[The three-in-a-tree problem](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.7221&rep=rep1&type=pdf)" by Chudnovsky and Seymour.


---

### Answer by username_9 on 2010-10-24. Score: 13

I think that it does not make much sense to talk about instances. We can talk about two distribution of input instances with different difficulties, but it would be more interesting if there is relation between the distribution, or between instances in the distributions.

We can consider a parameterized family of distributions, and then talk about what happens when we change the parameter. You might be interested in what is called the *threshold phenomenon*, "where a system undergoes a swift qualitative change as a result of a small change in a parameter ...". Take a look at this survey: [Ehud Friedgut](http://www.ma.huji.ac.il/~ehudf/), "[Hunting for Sharp Thresholds](http://www.ma.huji.ac.il/~ehudf/docs/survey.ps)", Random Structures Algorithms 26, 2005.

I think one of the most striking and beautiful examples is the random k-SAT with clause density $\Delta$, the phase transition is really amazing.


---

### Answer by username_10 on 2010-10-24. Score: 12

er ... i'm sure you're looking for less trivial examples... but I would like to point out that there's something special about the number $2$ vs $3$. $2-SAT$ to $3-SAT$, $2-COL$ vs $3-COL$, etc. Intuitively, I've always figured it was because a node with at most 2 edges can form at most a line, but a node with 3 edges can form a tree, when we move from 2-3 we get a combinatorial explosion.

> **Comments:**
> **username_11**: on the other hand, MAX 2SAT is hard. so 2 isn't THAT special.  
> **username_12**: 2 AND perfect completeness seem special though. :)  
> **username_0**: Also, 2D perfect matching vs 3D perfect matching.  

---

### Answer by username_13 on 2010-11-05. Score: 11

Inferring types for lambda terms is DEXPTIME-complete with [prenex](http://www.springerlink.com/index/7jhk84120120w4xr.pdf) and [rank-2](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.7215&rep=rep1&type=pdf) polymorphic type systems (when type quantifiers are nested at most one level deep), but becomes [undecidable](http://www.springerlink.com/index/m0m87453917r5g12.pdf) for rank-3 and higher. Strange that one extra nesting level can render a problem undecidable.


---

### Answer by username_14 on 2010-11-05. Score: 10

Finding ground state of planar Ising model with 0 magnetic field is in P, with non-zero magnetic field it is NP-hard. Partition function of planar Ising model with 0 magnetic field is in P, with non-zero magnetic field it is NP-hard.


---

### Answer by username_5 on 2013-04-29. Score: 9

Here is a nice problem with an interesting complexity jump like Minimum Bandwidth you
addressed in your question.

Let $G$ be a graph and $T$ a spanning tree of $G$. The detour for an edge
$uv\in E(G)$ is the unique $u$-$v$ path in $T$. The congestion of $e \in E(T)$,
denoted by $\mathrm{cng}\_{G,T}(e)$ is the number of detours that contain $e$.
The congestion of $G$ in $T$, denoted by $\mathrm{cng}\_G(T)$, is the maximum
congestion over all edges in $T$. The spanning tree congestion of $G$, denoted by
$\mathrm{stc}(G)$, is the minimum congestion over all spanning trees of $G$.
The Spanning Tree Congestion problem asks whether a given graph has spanning tree
congestion at most some given $k$.

The following complexity jump is shown in: [Bodlaender et al.,
*Parameterized Complexity of the Spanning Tree Congestion Problem*,
Algorithmica 64 (2012) 85–111](http://link.springer.com/article/10.1007%2Fs00453-011-9565-7):

For every fixed $k$ and $d$ the problem is solvable in linear time for graphs of degree at
most $d$. In contrast, if we allow **only one** vertex of unbounded degree, the problem immediately
becomes $\mathsf{NP}$-complete for any fixed $k\ge 8$.


---

### Answer by username_15 on 2010-11-06. Score: 8

I wonder why nobody mentioned this:

Horn-Sat vs K-Sat

I guess everybody knows what it is. If not:

Horn-Sat is to find if a set of horn clauses is satisfiable (each clause has at most 1 positive literal).

K-Sat is to find if a set of clauses is satisfiable (each clause can have more than 1 positive literals).

So allowing more than one positive literal in each clause makes the problem from P-complete NP-complete.


---

### Answer by username_15 on 2010-12-09. Score: 7

Graph Coloring

As mentioned in another answer, 2-COL is solvable in polynomial time while 3-COL is NP-complete.
But when increasing the number of colors, after some (unknown?) point the problem gets easier!

For example, if we have N vertices and N colors, the problem can be solved by assigning a different color to each vertex.

> **Comments:**
> **username_16**: ANY planar graph is 4-colorable.    [1]: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183538218  

---

### Answer by username_2 on 2010-10-26. Score: 6

In a similar vein: Permanent vs Determinant.

> **Comments:**
> **username_17**: The difference between perm and det is actually much more significant and of a different kind than the other hardness jumps discussed in the question and the other answers. Negation is *very* powerful: in a sense it's what allows us to compute det easily but not perm; Valiant has a paper "Negation can be exponentially powerful" http://portal.acm.org/citation.cfm?id=804412; lots of lower bounds are known for monotone complexity (even in the algebraic model, where monotonicity excludes negations and negative constants), but very few of these translate to non-monotone complexity.  
> **username_17**: Another example: negation is also necessary for Strassen's algorithm for multiplying 2x2 matrices.  Without it you cannot beat the trivial algorithm for multiplying 2x2 matrices.  

---

### Answer by username_18 on 2010-11-10. Score: 6

I just read a paper that deals with **hypergraph partitioning**. The Problem is defined as this, quote:

> Given two parameters $k$ and $l$, $1 \leq l < k$, the problem [$P^l\_k$] is defined as follows: Let $\mathcal{H} = (V, \mathcal{E})$ be a hypergraph and $t\_1, \dots, t\_k$ be non-negative integers such that $|V| = n = \sum^k\_{i=1} t\_i$ and $|\mathcal{E}| = m$. Does there exist a colouring (partition) of $V$ in $k$ subsets of size $t\_1, \dots, t\_k$ such that the vertices of each hyperedge in $\mathcal{E}$ are coloured with at most $l$ colours?

In general, it is proven that:

* $P^1\_k$ is solvable in polynomial time (in $n,m$) for fixed $k \geq 2$
* $P^l\_k$ is NP-complete for all fixed $2 \leq l < k$

If this is not "jump" enough, read on. For hypergraphs with disjoint hyperedges, it is shown:

* $P^1\_k$ is NP-complete for all fixed $k \geq 2$
* $P^l\_k$ is solvable in linear time (in $m$) for fixed $2 \leq l < k$

Laurent Lyaudet. 2010. NP-hard and linear variants of hypergraph partitioning. Theor. Comput. Sci. 411, 1 (January 2010), 10-21. <http://dx.doi.org/10.1016/j.tcs.2009.08.035>


---

### Answer by username_19 on 2010-12-10. Score: 5

Interesting complexity jumps are known for the job shop scheduling problem.

> In the job shop problem we have a set of $n$ jobs that must be processed on a given set $M$ of $m$ machines. Each job $j$ consists of a chain of $\mu\_j$ operations $O\_{1j},O\_{2j},\dots,O\_{\mu\_jj}$. Operation $O\_{ij}$ must be processed during $p\_{ij}$ time units without interruption on machine $m\_{ij}\in M$. A feasible schedule is one in which operation is scheduled only after all its preceding operations have been completed, and each machine processes at most one operation at a time. For any given schedule, let $C\_j$ be the completioon time of the last operation of job $j$. Taken [here](http://scholar.google.com/scholar?hl=en&num=100&q=%22Approximability+of+some+classical+graph+and+scheduling+problems%22&btnG=Search&as_sdt=2001&as_ylo=&as_vis=0).

There are such objectives as minimizing the makespan $C\_{max}=max\_jC\_j$ and total completion time $\sum C\_j$. Regular criteria are defined [here](http://books.google.com/books?id=MO5dVmXCQWcC&lpg=PA44&ots=-LFmLg0XM-&dq=%22regular%20criteria%22&pg=PA44#v=onepage&q=%22regular%20criteria%22&f=false).

> In the notation of [Graham et al.](http://www.math.ucsd.edu/%7Efan/ron/papers/79_03_scheduling_survey.pdf) this problem is denoted as $J||\gamma$, where $\gamma$ denotes the objective function to be minimized.
>
> $J2|n=k|F$ and $J|n=2|F$ are polynomially solvable. Here $J2$ $(n=k)$ means that the number of machines (jobs) is fixed and equals $2$ $(k)$. $F$ means an arbitrary regular criterion.
>
> $J3|n=3|C\_{max}$, $J3|n=3|\sum C$ are weakly NP-hard.
>
> $J2||C\_{max}$, $J2||\sum C$ are strongly NP-hard.

Thus, here we can see that there is a jump when we go from two jobs/machines to three.

> **Comments:**
> **username_0**: Good, I'm confused with the special terminology. Could you please simplify the terminology (or even better remove it)?  

---

### Answer by username_20 on 2019-01-03. Score: 1

In many cases, approximating NP-optimization problems give rise to sharp complexity jumps. For example, SET COVER can be approximated within a factor of $\ln n$ in polynomial time (by the Greedy Algorithm), but it is NP-hard to approximate within a factor of $(1-o(1))\ln n$.


---

### Answer by username_21 on 2018-12-31. Score: 0

I think the [pascal triangle](https://en.m.wikipedia.org/wiki/Pascal%27s_triangle?wprov=sfla1) would be it. Each row in the pascal triangle sums to $2^n$. The elements are binomial coefficients. So if you find a problem whose performance can be described using binomial coefficients, then simply solving all such problems associated to the n'th row of the pascal triangle already takes $2^n$. But note that $(a+b)^n=\sum\_{i\in{0..n}}{{n}\choose{i}}a^ib^{n-i}$ can be represented as a polynomial (of 'a') that has binomial coefficient times powers of 'b' as factors. If 'b' is constant this is a n'th order polynomial $p\_b(a)$. Setting $a=b=1$ you get expansion of $2^n=p\_1(1)$ as a sum. Now suppose you have a matrix of problems with performance in two variables proportional to binomial coefficients (compared to problem *size* described by two variables) arranged like a pascal triangle. Then solving all problems in n'th row must take $DTIME(2^n)$. Binomial coefficients describe how many different ways there are to choose k-combinations from n elements. So if your algorithm depends on enumerating k-combinations of n elements $(k the algorithm cannot be polynomial time. Because if this problem was polynomial time, then above argument proves $P=NP=DTIME(2^n)$, since sum of two polynomials is a polynomial. But correct proofs of $P=NP$ problem either way are rare.


---

