Hardness jumps in computational complexity?

Question

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?

Answer 1

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)

Answer 2

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.

Answer 3

INDEPENDENT SET is NP-complete for (cross,triangle)-free graphs, but can be solved in linear time for (chair,triangle)-free graphs. (The X-free graphs are those that contain no graph from X as an induced subgraph.)

chair: triangle: cross:

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

Answer 4

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

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 5

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:

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" 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" by Chudnovsky and Seymour.

Answer 6

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, "Hunting for Sharp Thresholds", 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 7

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.

Answer 8

Inferring types for lambda terms is DEXPTIME-complete with prenex and rank-2 polymorphic type systems (when type quantifiers are nested at most one level deep), but becomes undecidable for rank-3 and higher. Strange that one extra nesting level can render a problem undecidable.

Answer 9

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 10

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:

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 11

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 12

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.

Answer 13

In a similar vein: Permanent vs Determinant.

Answer 14

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 15

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.

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.

In the notation of Graham et al. 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.

Answer 16

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 17

I think the pascal triangle 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<n)$ 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.