Hubbry Logo
List of NP-complete problemsList of NP-complete problemsMain
Open search
List of NP-complete problems
Community hub
List of NP-complete problems
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
List of NP-complete problems
List of NP-complete problems
List of NP-complete problems
View on Wikipedia
from Wikipedia

This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands of such problems known, this list is in no way comprehensive. Many problems of this type can be found in Garey & Johnson (1979).

Graphs and hypergraphs

[edit]

Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. Facebook or LinkedIn).

NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.[3]: ND2 
NP-complete special cases include the minimum maximal matching problem,[3]: GT10  which is essentially equal to the edge dominating set problem (see above).

Mathematical programming

[edit]

Formal languages and string processing

[edit]

Games and puzzles

[edit]

Other

[edit]

See also

[edit]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

List of NP-complete problems

View on Grokipedia
from Grokipedia
A list of NP-complete problems refers to a catalog of decision problems in that belong to the class NP (nondeterministic polynomial time) and to which every other problem in NP can be reduced via a polynomial-time , establishing their central role in understanding computational intractability. These problems, first formally defined through the satisfiability problem (SAT) by in 1971, capture a wide array of fundamental challenges across , , optimization, and other disciplines, where verifying a proposed solution is efficient but finding one is presumed hard. In 1972, Karp expanded this foundation by demonstrating that 21 diverse combinatorial problems—spanning areas like (e.g., Hamiltonian circuit, ), (e.g., ), and numerical computation (e.g., subset sum)—are NP-complete via reductions from SAT, highlighting the ubiquity of such hardness. By 1979, Michael Garey and David Johnson's seminal book Computers and Intractability compiled over 300 such problems, providing proofs, references, and classifications that standardized the field. Today, thousands of NP-complete problems are known, encompassing applications in scheduling, network design, , biology (e.g., protein folding variants), and beyond, with ongoing research continually identifying new instances while the P vs. NP question remains unresolved. This entry surveys notable examples, grouped by domain, illustrating their reductions and significance.

Fundamentals

Definition and Properties

NP (nondeterministic polynomial time) is the complexity class consisting of decision problems for which a "yes" instance can be verified in polynomial time using a , meaning there exists a -time path that accepts the input if it is in the language. Equivalently, NP contains languages L for which there is a deterministic -time verifier V such that for every input x in L, there exists a short certificate y (of length in |x|) where V(x, y) accepts, and for x not in L, no such y exists. A problem is NP-hard if every problem in NP can be reduced to it via a polynomial-time , implying that an efficient algorithm for an NP-hard problem would solve all of NP efficiently. The NP-complete problems form the intersection of NP and NP-hard sets; thus, a problem is NP-complete if it is in NP and every NP problem reduces to it in time, with the key property that a -time algorithm for any NP-complete problem would imply P = NP, placing all of NP in P. The foundational result establishing the existence of NP-complete problems is the Cook-Levin theorem, proved by Stephen A. Cook in 1971, which shows that the (SAT)—deciding whether there exists a truth assignment satisfying a given Boolean formula—is NP-complete. The proof constructs a from any NP problem to SAT: given a M deciding an NP language in polynomial time, simulate p steps of M on input x using a C of size polynomial in p, where the circuit's gates represent the machine's configuration transitions; then, SAT on the formula encoding C's satisfiability corresponds to M accepting x nondeterministically. This reduction demonstrates that SAT captures the full expressive power of NP verification. NP-complete problems exhibit closure under polynomial-time many-one reductions: if A is NP-complete and there is a from A to B with B in NP, then B is also NP-complete, allowing the propagation of hardness across problems. This property underscores the interconnectedness of NP-complete problems and amplifies the significance of the P versus NP question, as resolving it for one would resolve it for all. In , Richard M. Karp extended Cook's result by showing that 21 natural combinatorial problems are NP-complete via reductions from SAT, including (does a graph have a of size at least k?), (does a graph have a of size at most k?), Independent Set, Hamiltonian Cycle, and 3-SAT (satisfiability of a 3-conjunctive normal form formula). As a canonical example, 3-SAT asks whether there exists a Boolean assignment satisfying a formula in 3-CNF, where each has exactly three literals; it is NP-complete because SAT reduces to it in time by , and it remains in NP via direct verification of satisfying assignments.

Historical Development

The concept of was formally introduced in 1971 by in his seminal paper "The Complexity of Theorem-Proving Procedures," where he defined the classes and NP and proved that the (SAT) is NP-complete via polynomial-time reductions. Independently, discovered similar results around the same time, with his work published in 1973. This work established a framework for identifying the hardest problems in NP, analogizing them to complete problems in recursive function theory but using polynomial-time reductions instead of many-one reductions. In 1972, Richard Karp built on Cook's foundation in his paper "Reducibility Among Combinatorial Problems," demonstrating that 21 diverse problems—spanning , logic, and optimization, such as the and traveling salesman problem—are NP-complete by reducing SAT to each of them. Karp's reductions highlighted the broad applicability of across combinatorial domains, sparking widespread interest in classifying other problems. By 1979, Michael Garey and David S. Johnson compiled an extensive catalog in their book Computers and Intractability: A Guide to the Theory of NP-Completeness, documenting over 300 NP-complete problems with proofs and practical insights, serving as a foundational reference for researchers. Post-1980 developments extended to approximation algorithms, with the probabilistically checkable proofs ( in the —culminating in results like and Safra's 1992 work and the full theorem in —proving that many NP-complete optimization problems are inapproximable within certain factors unless P=NP. In 2000, the designated the as one of its seven , offering a $1 million reward for a resolution, underscoring its centrality to . During the and , gained recognition in real-world applications, including scheduling tasks in and hardness assumptions in protocols like those based on lattice problems. As of 2025, thousands of NP-complete problems have been identified across fields like and logic, yet no polynomial-time algorithm has been found for any, despite advances in such as for factoring, which do not resolve general . This ongoing absence reinforces the presumed intractability of NP-complete problems and drives research into heuristics and parameterized approaches.

Graph and Network Problems

Vertex and Independence Problems

The vertex and independence problems in focus on selecting subsets of vertices that satisfy specific structural conditions, such as mutual non-adjacency or coverage of edges and neighborhoods. These problems are fundamental in and arise in applications like network design, , and bioinformatics. Their decision versions—determining whether a qualifying set of a given size exists—are among the NP-complete problems, establishing their computational hardness even for moderate-sized instances. The Independent Set problem asks whether a given undirected graph G=(V,E)G = (V, E) and integer kk admit an independent set—a subset of vertices with no two adjacent—of size at least kk. This problem is in NP, as a proposed set can be verified for independence and size in polynomial time. It is NP-hard by from the : the G‾\overline{G} has an independent set of size kk if and only if GG has a clique of size kk. Thus, Independent Set is NP-complete. The optimization variant seeks the maximum independent set, which is APX-hard, meaning no constant-factor approximation exists unless P = NP. Closely related is the , which determines whether GG contains a —a complete subgraph—of size at least kk. is in NP via verification of all pairwise edges in a proposed set. Karp established its via reduction from 3-SAT, constructing a graph where clauses and variables form gadgets ensuring a satisfying assignment corresponds to a large . The decision version complements Independent Set, as cliques in GG are independent sets in G‾\overline{G}, and the maximum clique optimization is similarly intractable. The problem inquires whether GG has a vertex cover—a set of vertices incident to every edge—of size at most kk. Membership in NP follows from checking that no edge lies outside the neighborhood of the proposed cover. NP-hardness arises from reduction from : for a graph HH and kk, form GG as the complement of HH; then HH has a clique of size kk if and only if GG has a vertex cover of size ∣V(H)∣−k|V(H)| - k. Hence, Vertex Cover is NP-complete, with the minimum vertex cover optimization being a core hard problem in approximation algorithms. Notably, Vertex Cover remains NP-complete even for planar graphs with maximum degree 4. The problem asks if GG admits a —a subset S⊆VS \subseteq V such that every vertex not in SS is adjacent to some vertex in SS—of size at most kk. It is in NP, verifiable by inspecting neighborhoods. Garey, Johnson, and Stockmeyer proved via reduction from by 3-Sets, restricting to planar graphs of maximum degree 3, where the construction preserves planarity and ensures a dominating set corresponds to a cover. The minimum dominating set optimization has variants like connected dominating sets, which remain NP-hard. is NP-complete even on planar graphs. Finally, the problem determines whether removing at most kk vertices from GG yields an acyclic graph (). It is in NP, as the remaining graph's acyclicity can be checked via topological sort or . follows from reduction from : subdivide each edge of the input graph and add gadgets to force cycles that must be hit precisely by the cover. For directed graphs, Karp showed via 3-SAT reduction, implying hardness for the undirected case. The minimum feedback vertex set is even on tournaments and planar graphs. Many of these problems, including Independent Set, , and , retain when restricted to planar graphs, highlighting their robustness to geometric constraints.

Connectivity and Path Problems

Connectivity and path problems in focus on the existence of traversals that visit vertices or edges in specific ways while maintaining connectivity. These problems are central to network design, , and optimization, where finding efficient paths or connected substructures is crucial. Many such problems are NP-complete, meaning that verifying a solution is polynomial-time feasible, but no known polynomial-time algorithm exists for solving them in general, assuming P ≠ NP. Seminal reductions often trace back to 3-SAT or other core NP-complete problems, highlighting their intractability even in restricted graph classes like grids or bounded-degree graphs. The Hamiltonian Path problem asks whether an undirected graph G = (V, E) contains a path that visits each vertex in V exactly once. This decision problem is NP-complete, proven via a polynomial-time reduction from 3-SAT, where clauses and variables are encoded into graph structures that force a Hamiltonian path if and only if the formula is satisfiable. The problem remains NP-complete even for restricted cases, such as grid graphs (rectangular arrays of vertices with edges between adjacent ones) and cubic graphs (maximum degree 3), where reductions from bipartite matching or planar graphs preserve the hardness. For example, in an m × n grid graph, determining a Hamiltonian path is NP-complete for m, n ≥ 2, as shown by constructing grids from planar 3-regular bipartite graphs. Closely related is the Hamiltonian Cycle problem, which seeks a cycle visiting each vertex exactly once. It is also NP-complete by reduction from 3-SAT, similar to the path variant, and serves as a basis for other hardness results. The decision version of the Traveling Salesman Problem (TSP)—given a with edge weights and bound k, does there exist a Hamiltonian cycle of total weight at most k?—is NP-complete via a direct reduction from Hamiltonian Cycle: assign weight 1 to original edges and 2 to added ones, ensuring a cycle of weight at most |V| exists if and only if the original graph has a Hamiltonian cycle. This connection underscores TSP's role in routing applications, where exact solutions are intractable for large instances. The ** in graphs, given a graph G = (V, E), a subset of terminals W ⊆ V, and integer k, asks if there exists a subtree of G connecting all vertices in W using at most k edges. This is NP-complete, reduced from the by 3-Sets problem, where sets correspond to potential Steiner vertices that connect disjoint components only if the cover exists. The reduction constructs a graph where minimal connecting trees mirror exact covers, preserving the decision outcome. The problem is particularly relevant in network design, as it allows additional (Steiner) vertices to minimize connection costs. The (CPP) seeks a closed walk in a connected graph that traverses each edge at least once, minimizing total length. For undirected graphs, it is solvable in polynomial time via matching on odd-degree vertices. However, for mixed graphs (containing both undirected edges and directed arcs), the decision version—does such a walk of length at most k exist?—is NP-complete, proven by reduction from TSP, where orienting edges and adding arcs encodes tour constraints that force edge traversals to match a Hamiltonian cycle if satisfiable. This hardness arises because mixed graphs lack the Eulerian properties of pure undirected or directed cases, requiring complex pairing of unpaired paths. A Connected Dominating Set is a dominating set S ⊆ V such that the induced subgraph G[S] is connected, meaning every vertex is either in S or adjacent to S, and S forms a connected structure. The minimum connected dominating set problem—given G and k, does there exist such an S with |S| ≤ k?—is NP-complete, shown via reduction from the maximum leaf spanning tree problem, where connected dominators correspond to trees with bounded internal vertices. This extends the NP-completeness of dominating set by enforcing connectivity, which adds the challenge of spanning without disconnects. The problem is vital for efficient in networks, where the set acts as a connected backbone.

Coloring and Covering Problems

The graph coloring problem determines whether the vertices of an undirected graph G=(V,E)G = (V, E) can be assigned colors from a set of at most kk colors such that no two adjacent vertices receive the same color. This is in NP, as a proposed coloring can be verified in polynomial time by checking each edge. It is NP-complete for any fixed integer k≥3k \geq 3, established via reduction from 3-satisfiability through intermediate problems like 3-dimensional matching. The chromatic number decision problem asks whether the chromatic number χ(G)\chi(G), defined as the minimum number of colors needed for a proper vertex coloring of GG, is at most kk. This is equivalent to the kk-coloring problem and thus NP-complete for k≥3k \geq 3. A notable restricted case is 3-coloring of planar graphs, which remains NP-complete; the proof involves a from general 3-coloring that preserves planarity using gadgets to handle edge crossings.90059-1) Furthermore, 3-coloring is NP-complete even for planar graphs with maximum degree 4, via a local replacement reduction that bounds vertex degrees without increasing the number of colors required. The , in a graph-theoretic variant, considers the vertices of a graph (or ) as the universe and the incident edges (or hyperedges) as subsets; the task is to select at most kk such subsets to cover every vertex at least once. While the standard edge cover in simple graphs (where subsets are 2-element sets) is solvable in polynomial time via maximum matching algorithms, the general version with arbitrary hyperedges is NP-complete, reduced from or problems. The by 3-sets (X3C) problem asks whether a given collection of 3-element subsets of a of size 3m3m contains an , i.e., mm disjoint subsets whose union is the entire set. This problem is NP-complete, proven by reduction from 3-satisfiability, and serves as a canonical example in set partitioning; it generalizes to by rr-sets for r≥3r \geq 3.

Optimization and Programming Problems

Integer and Constraint Programming

and encompass a range of decision problems involving the satisfaction of linear or nonlinear constraints over or discrete domains, many of which are NP-complete. These problems arise naturally in optimization, scheduling, and , where finding feasible solutions requires searching vast combinatorial spaces. The NP-completeness of these problems stems from their ability to encode other hard combinatorial structures, such as , through reductions that preserve computational difficulty. A foundational NP-complete problem in this area is 0-1 Integer Linear Programming (0-1 ILP), which asks whether there exists a vector x∈{0,1}nx \in \{0,1\}^n satisfying a system of linear inequalities Ax≤bAx \leq b, where AA is an m×nm \times n integer matrix and bb is an integer vector. This problem is NP-complete, as it generalizes the problem and admits polynomial-time reductions from known NP-complete tasks like 3-SAT. For instance, the —determining if there is a subset of integers summing to a target value—reduces directly to 0-1 ILP by encoding selection variables xi∈{0,1}x_i \in \{0,1\} in the single inequality ∑aixi=t\sum a_i x_i = t. More generally, Integer Linear Programming feasibility, which seeks integer solutions x∈Znx \in \mathbb{Z}^n to Ax≤bAx \leq b, is also NP-complete. This holds even when the number of inequalities (constraints) is fixed, such as in the case of a single linear ∑aixi=b\sum a_i x_i = b with non-negative integers xix_i, a variant known as the unbounded , which remains NP-complete despite allowing multiple uses of each coefficient. In contrast, when the number of variables is fixed, the problem becomes solvable in polynomial time via lattice-based algorithms, highlighting the role of dimensionality in complexity. However, the general case with variable dimensions underscores its intractability. Constraint Satisfaction Problems (CSPs) formalize another core NP-complete challenge: given a set of variables, a domain of possible values for each, and a collection of constraints specifying allowed combinations, does there exist an assignment satisfying all constraints? The general CSP is NP-complete, as it encompasses problems like graph coloring and directly reduces from 3-SAT by treating boolean variables and clauses as binary or ternary constraints over a domain of size 2. Even restricted variants, such as 3-CSP with ternary constraints, retain NP-completeness, making CSP a versatile framework for modeling discrete optimization. Extending to nonlinear settings, the problem of solving quadratic Diophantine equations—determining if there exist x1,…,xnx_1, \dots, x_n such that ∑i,jaijxixj=0\sum_{i,j} a_{ij} x_i x_j = 0, with integer coefficients aija_{ij}—is NP-complete. This result follows from reductions showing that even simpler forms, like αx2+βy−γ=0\alpha x^2 + \beta y - \gamma = 0 with non-negative α,β,γ\alpha, \beta, \gamma and variables x,yx, y, capture the full hardness of NP. Such equations bridge and complexity, with proofs relying on encodings of subset sum and partitioning problems into quadratic forms.

Packing and Partitioning Problems

Packing and partitioning problems in involve determining whether a collection of items or numbers can be divided into subsets that satisfy specific sum or capacity constraints, often arising in and optimization scenarios. These problems are fundamental examples of NP-complete decision problems, meaning that verifying a proposed solution is efficient, but finding one is believed to be computationally intractable in the worst case. They typically feature integer inputs and focus on exact matches or bounds, distinguishing them from broader formulations by their emphasis on subset selections without additional variables or inequalities. The Subset Sum problem asks whether, given a set of positive integers S={s1,s2,…,sn}S = \{s_1, s_2, \dots, s_n\} and a target integer tt, there exists a subset of SS whose elements sum exactly to tt. This problem is NP-complete, as shown through a reduction from the 3-SAT problem in Karp's seminal work on combinatorial reducibility. It remains NP-complete even when the integers in SS and tt are polynomially bounded in the input size, highlighting its inherent hardness beyond mere large number representations. However, Subset Sum admits a dynamic programming algorithm that runs in O(nt)O(n t) time, which is efficient when tt is small relative to the input length but exponential in the of tt. A direct generalization is the problem, which determines whether a of positive integers A={a1,a2,…,an}A = \{a_1, a_2, \dots, a_n\} can be divided into two subsets with equal sums (assuming the total sum is even). This is NP-complete, proven by a straightforward reduction from Subset Sum: given an instance of Subset Sum with target tt, construct a Partition instance by adding a new element equal to the total sum minus tt and adjusting accordingly. Like Subset Sum, Partition has a pseudo-polynomial dynamic programming solution but is weakly NP-complete, meaning its hardness relies on the magnitude of the numbers rather than their count alone. The 0-1 Knapsack decision problem extends these ideas to dual constraints: given items each with a weight wiw_i and value viv_i, a knapsack capacity WW, and a value threshold VV, does there exist a of items such that the total weight is at most WW and the total value is at least VV, with each item either fully included or excluded? This variant is NP-complete, established via reduction from Partition by setting values equal to weights and choosing appropriate VV and WW. It models real-world scenarios like cargo loading under weight limits while maximizing utility, and while pseudo-polynomial algorithms exist (e.g., O(nWV)O(n W V) dynamic programming), the problem's holds for polynomially bounded inputs. In the Bin Packing decision problem, the task is to decide whether nn items with sizes s1,s2,…,sns_1, s_2, \dots, s_n (each si≤Cs_i \leq C) can be packed into at most kk bins, each of capacity CC, without splitting items. This is NP-complete, shown by reduction from Partition: map each partition element to an item of that size and set CC to half the total sum with k=2k = 2. Bin Packing is weakly NP-complete, with approximation algorithms achieving factors close to optimal, but exact solutions require exponential time in general. For stronger intractability, the 3-Partition problem requires partitioning a set of 3m3m positive integers into mm disjoint triples, each summing exactly to a bound BB (where the total sum is mBmB and each integer is between B/4B/4 and B/2B/2). This is strongly NP-complete, meaning it remains NP-complete even under unary encoding of inputs, proven via reduction from 3-SAT or numerical matching problems without relying on large numbers. Unlike the previous problems, 3-Partition lacks pseudo-polynomial algorithms due to its structural constraints on subset sizes, making it a key tool for proving hardness in scheduling and resource problems with fixed group cardinalities.

Scheduling and Allocation Problems

Scheduling and allocation problems involve assigning resources, tasks, or labels to entities under constraints involving time, costs, or capacities, often with the goal of meeting deadlines or minimizing maximum loads. These problems frequently arise in manufacturing, logistics, and computer systems design, where sequencing and distribution decisions impact efficiency. Unlike static partitioning problems, such as those in load balancing via partitioning, scheduling incorporates temporal or ordering elements that introduce sequencing dependencies, making them computationally challenging. The decision versions of many such problems, asking whether a feasible assignment exists within given bounds, are NP-complete, highlighting their intractability even for moderate instance sizes. The problem requires assigning a set of jobs, each consisting of operations that must be processed on specific machines in a fixed order, to time slots on those machines without overlaps, such that all jobs complete by a given deadline. This models flexible systems where machine availability and job precedence must be respected. The —determining if there exists a schedule meeting the deadline—is NP-complete, even for instances with two or more machines, as shown through reductions from known NP-complete problems like 3-SAT. Seminal work established this complexity by classifying various machine scheduling variants, demonstrating strong for the case. A specific instance of scheduling complexity is the multiprocessor scheduling problem on multiple identical processors to minimize makespan with arbitrary processing times, where the goal is to assign jobs to processors such that the maximum completion time () is at most a given value k. This problem captures resource distribution in environments, where balancing workloads across processors is essential. The decision version is NP-complete when the number of processors is part of the input, proven in the 1970s via reductions from partitioning problems, establishing strong even without precedence constraints. The (VRP) decision version asks whether a fleet of vehicles, starting from a depot, can serve a set of customers with given demands such that each customer is visited exactly once and the total distance traveled by all vehicles is at most k, respecting vehicle capacities. This models distribution logistics, where route planning minimizes travel while ensuring coverage. The problem is NP-complete, even in its capacitated form without time windows, via reduction from the Hamiltonian cycle problem or , with early proofs confirming its intractability for practical fleet sizes. The graph bandwidth problem requires labeling the vertices of an undirected graph with distinct integers from 1 to n such that the maximum in labels over all edges is at most b. This minimization problem relates to matrix bandwidth reduction for efficient computations and network layout optimization. The decision version—whether such a labeling exists for a given b—is NP-complete for general graphs, proven by reduction from or similar problems, with the seminal result establishing its hardness even on simple graph classes.

Logic and Language Problems

Satisfiability and Formula Evaluation

The (SAT) asks whether there exists a truth assignment to the variables of a given Boolean formula in (CNF) such that the formula evaluates to true. SAT was the first problem proven to be NP-complete, establishing it as a cornerstone of through the Cook-Levin theorem, which demonstrates that any problem in NP can be reduced to SAT in time. This reduction involves simulating the nondeterministic Turing machine computation for an NP problem using a and encoding the acceptance condition as a CNF formula. A prominent restricted variant, 3-SAT, limits each clause in the CNF formula to exactly three literals and remains NP-complete, as shown by a from general SAT that pads clauses with auxiliary variables to achieve the three-literal bound. This variant is particularly useful for proving of other problems due to its structured yet intractable nature. Circuit satisfiability (CSAT), which determines whether there exists an input assignment that makes a given output true, is also NP-complete and forms the basis of the Cook-Levin construction, where the circuit simulates the NP verifier. Monotone variants of SAT, which restrict literals to be either all positive or all negative, include positive 1-in-3 SAT, where each of three positive literals must have exactly one true literal under some assignment; this problem is NP-complete as a special case within Schaefer's dichotomy theorem on generalized . Similarly, negative 1-in-3 SAT, using only negated literals, shares this NP-completeness. Exact , requiring exactly one true literal per in a CNF formula, is likewise NP-complete under Schaefer's classification, distinguishing it from standard SAT by its stricter per-clause condition. As of 2025, modern SAT solvers, employing techniques like and look-ahead branching, routinely solve industrial-scale instances with millions of variables and clauses arising from verification and optimization tasks, though no polynomial-time algorithm exists assuming P ≠ NP.

String and Sequence Processing

In string and sequence processing, several decision problems involving the manipulation and comparison of sequences over finite s are NP-complete, highlighting the computational challenges in theory and bioinformatics applications. One such problem is the (LCS) decision version for multiple sequences: given k strings (k ≥ 3) over a general alphabet and an integer l, determine if there exists a common of length at least l. This problem is NP-complete, as shown by reductions from known NP-complete problems like 3-SAT, even under restrictions such as small alphabet sizes or bounded run-length encodings. The NP membership follows from guessing the positions in each and verifying the subsequence in polynomial time, while hardness arises from the in aligning multiple sequences without a polynomial-time dynamic programming solution applicable beyond two strings. Another key NP-complete problem in this domain is with gaps, where the task is to align k ≥ 3 sequences (k ≥ 3) such that the total score—accounting for matches, mismatches, and gap penalties—exceeds a threshold, under models like the sum-of-pairs (SP) score. This is NP-complete for general scoring matrices, including those used in biological , via reductions from or problems that encode alignment costs to enforce structural constraints. The problem's intractability stems from the exponential number of possible alignments, though dynamic programming solves the pairwise case efficiently. Regular expression matching with capture groups (backreferences) is also NP-complete: given a regular expression with backreferences and a string, decide if there is a match where captured subgroups are reused exactly as specified. This extends standard regex matching beyond regular languages into context-sensitive territory, with NP-completeness proven by reduction from 3-SAT, where clauses are encoded as patterns requiring backreference consistency. Verification involves nondeterministically choosing capture positions and checking substring equality, polynomial in the input size. Regarding palindromes in the context of formal languages, deciding whether a given admits a factorization into distinct palindromic factors—each appearing uniquely in the decomposition—is NP-complete, even over binary alphabets. This problem relates to recognition in ambiguous or non-standard derivations, as palindromic structures can model certain -free ambiguities, reduced from circuit satisfiability by encoding circuit computations into structures that require unique palindromic covers for satisfying assignments. Notably, while the membership problem for context-free languages—determining if a belongs to the language generated by a given —is solvable in polynomial time using algorithms like Cocke-Younger-Kasami or Earley , optimization variants such as finding the smallest context-free grammar generating exactly a given (the smallest grammar problem) are NP-complete. This involves minimizing the total size of production rules, proven NP-hard by reduction from 3-partition, capturing the difficulty of compressing sequences via hierarchical derivations.

Game and Puzzle Problems

Combinatorial Puzzles

Combinatorial puzzles represent a class of NP-complete problems where the task involves configuring fixed-rule elements, such as pieces or positions, to satisfy specific constraints without interactions between multiple agents. These problems often model spatial arrangements and have been shown to be NP-complete through reductions from known hard problems like 3-SAT or , highlighting their computational intractability for general instances. The N-Queens completion problem asks whether a partially placed set of queens on an n × n can be extended to a full configuration where no two attack each other, meaning no shared row, column, or diagonal. This is NP-complete. Solutions exist for the empty board when n ≥ 4, but completion introduces exponential search complexity in the worst case. Sudoku completion determines if a partially filled 9 × 9 grid, divided into nine subgrids, can be completed such that each row, column, and subgrid contains the digits 1 through 9 exactly once. This problem is NP-complete, following from the NP-completeness of Latin square completion via a straightforward reduction that embeds Sudoku constraints into a larger instance. Even with rectangular hole patterns in the grid, the problem remains NP-complete, underscoring its robustness to structural variations. For the , the problem of deciding whether a given scrambled n × n × n cube configuration can be solved in at most k moves is NP-complete. This result holds by reducing from the Hamiltonian cycle problem in square grid graphs, where cube moves simulate graph traversals, proving while the problem is clearly in NP due to verifiable short solutions. The proof applies to general positions, including those reachable only through disassembly, emphasizing the challenge for larger n. The assembly problem involves deciding whether a given of —unit squares with colored edges—can tile a without gaps or overlaps, matching colors on adjacent edges. Tiling a with a fixed set of such tiles is NP-complete, as demonstrated by reductions from 3-SAT that encode variable assignments and clause satisfactions into tile placements and color matchings. This finite variant contrasts with the undecidable infinite plane tiling but captures the core hardness of models. Instant Insanity requires stacking four cubes, each with colored faces, such that each side of the stack shows four different colors. This puzzle is NP-complete. As of 2025, solvers for Instant Insanity and similar combinatorial puzzles predominantly rely on algorithms to explore configurations, offering no polynomial-time guarantees due to the underlying .

Adversarial and Strategy Games

In adversarial and strategy games, determining optimal play often involves complex decision problems due to alternating moves and strategic interactions, but certain subproblems—such as existence of winning sequences or identification of irrelevant positions—fall into NP-complete territory. These arise in variants where the focus shifts to verifiable paths or configurations rather than full game-tree exploration. A prominent example is generalized solo chess, a single-player adaptation where pieces of the same color maneuver on an n × n board to capture an opposing king without opposition moves. The decision problem—whether there exists a sequence of moves achieving checkmate—is NP-complete, even restricted to rooks with at most two captures each. This hardness stems from reductions involving bounded nondeterminism in piece movements, mirroring challenges in reconfiguration problems. In the board game Hex, played on an n × n hexagonal grid where players connect opposite sides, the core problem of determining a winning strategy for the first player is . A related subproblem in the , which generalizes aspects of Hex, is NP-complete: deciding whether a given empty cell is "dead," meaning its occupation by either player does not affect the game's theoretical outcome. This has been proven NP-complete via reduction from 3-SAT and is applicable even in partially filled boards. Analyses in the 2020s have extended this to bounded configurations, aiding practical solvers by pruning irrelevant cells. The , where players alternately name distinct places (e.g., cities) such that each starts with the last letter of the previous, without repetition, models strategic naming under constraints. The two-player version on graphs—generalized geography—is PSPACE-complete, as it encodes alternating quantifiers over paths. A natural NP-complete variant asks whether there exists a sequence covering all places without letter repetition violations, equivalent to finding a Hamiltonian path in the directed graph where vertices are places and edges connect those with matching ending/starting letters; this is NP-complete by standard reductions from Hamiltonian path problems. Kayles, an impartial node-deletion game on graphs where players alternately remove a vertex and its neighbors (simulating knocking down one or two adjacent pins), has its standard normal-play winning strategy decision . For misère Kayles—where the last move loses—the problem remains , as shown by reductions preserving the exponential while adjusting terminal conditions; no polynomial certificate exists beyond short games, but subproblems like bounded-length play sequences exhibit akin to independent set maximization. The , a maker-breaker variant on graphs where one player shorts edges to connect terminals and the other cuts to disconnect, is PSPACE-complete in general. Identifying "dead" vertices—those irrelevant to any winning strategy regardless of play—is NP-complete, reducible from ; this holds for planar graphs and has been confirmed in 2020s extensions to bounded-move scenarios, where limited turns make certificate verification feasible in polynomial time.

Emerging and Miscellaneous Problems

Algebraic and Number-Theoretic Problems

Algebraic and number-theoretic problems in involve decision questions about solutions to equations or embeddings in structures defined over integers or finite algebraic systems. These problems bridge , , and complexity theory, often reducing from known NP-complete problems like 3-SAT or subset sum to demonstrate hardness. While many such problems are in NP due to short verifiable witnesses (e.g., a solution or mapping), their completeness arises from intricate preserving algebraic , such as operation preservation or modular constraints. Seminal works in the 1970s established foundational results, showing that even restricted forms of classical unsolved problems like Hilbert's tenth are NP-complete, underscoring the intractability of exact solvability in these domains. A key example is the of solving quadratic Diophantine equations in two variables. Consider the : given nonnegative integers α,β,γ\alpha, \beta, \gamma, does there exist natural numbers x1,x2x_1, x_2 such that αx12+βx2=γ\alpha x_1^2 + \beta x_2 = \gamma? This problem is in NP, as a solution pair (x1,x2)(x_1, x_2) can be verified in time by direct substitution and multiplication. It is NP-hard by reduction from 3-SAT, constructing coefficients that encode clause satisfiability through quadratic forms, and thus NP-complete. This hardness extends to quadratic congruences modulo composite numbers. The problem asks: given nonnegative integers α,β,γ\alpha, \beta, \gamma with the prime of β\beta provided, does there exist an integer xx such that 0<x<γ0 < x < \gamma and x2≡α(modβ)x^2 \equiv \alpha \pmod{\beta}? Membership in NP follows from verifying the congruence and bound using . is established via reduction from the quadratic Diophantine problem above, mapping solutions to residues while handling the composite modulus through the given factorization, making the problem NP-complete even when solutions are bounded. Hilbert's tenth problem, posed in 1900, seeks an algorithm to decide if a multivariate equation with coefficients has nonzero solutions; it is undecidable in general, as proven by Matiyasevich in 1970 building on Davis-Putnam-Robinson results. However, restrictions to bounded variables or specific forms yield decidable yet hard cases. In particular, the version restricted to quadratic equations in two variables—determining if ax2+by=ca x^2 + b y = c has positive solutions x,yx, y for given nonnegative integers a,b,ca, b, c—is NP-complete. It is in NP via solution verification, and NP-hard by reduction from 3-SAT, as shown in the original proof constructing coefficients to encode clause satisfiability. In , problems involving embeddings or s between finite structures that preserve operations are often NP-complete. For instance, the homomorphism factorization problem for finite s asks: given finite semigroups X,Y,ZX, Y, Z and a f:X→Zf: X \to Z, does there exist a finite semigroup Y′Y' and homomorphisms g:X→Y′g: X \to Y', h:Y′→Zh: Y' \to Z such that f=h∘gf = h \circ g? This is in NP, as a candidate Y′Y', gg, and hh can be checked for composition and operation preservation in time relative to input sizes. NP-hardness follows from reductions involving problems over semigroup varieties, such as encoding graph colorings into semigroup actions, rendering the problem NP-complete for general finite semigroups. A related challenge appears in partial factoring decisions, where one asks if a composite nn has a nontrivial factor in a specified interval [a,b][a, b] with 1<a≤b<n1 < a \leq b < n. This variant is in NP, verifiable by division, but its completeness status is nonstandard; it is NP-hard under randomized reductions from problems like one-in-three SAT, though deterministic polynomial-time reductions remain open, highlighting distributional hardness in cryptographic contexts.

Approximation and Modeling Problems

The decision version of the problem, which asks whether a given protein sequence can fold into a target three-dimensional conformation under simplified models such as the hydrophobic-hydrophilic (HP) lattice model, is . This result establishes the computational hardness of predicting stable protein s, a key challenge in , where reductions from known problems like 3-dimensional matching demonstrate the intractability even for coarse-grained representations. In biological sequence folding more broadly, coverage remains sparse, with NP-completeness proven primarily for protein models, while tertiary prediction under certain models also exhibits similar hardness, though secondary structure folding is tractable via dynamic programming. The Traveling Salesman Problem with Neighborhoods (TSPN) generalizes the classic TSP by allowing the tour to visit regions or neighborhoods rather than exact points, accommodating imprecise locations in applications like or ; its decision version, determining if a tour of length at most a given bound exists, is NP-complete. This hardness follows from reductions from the standard TSP, preserving the while introducing flexibility for real-world modeling of uncertainty in spatial data. Approximation algorithms achieve constant-factor guarantees for Euclidean instances, highlighting the problem's relevance in geometric optimization despite intractability. In directed graphs, the Minimum problem seeks the smallest set of arcs whose removal renders the graph acyclic, and for tournaments—complete oriented graphs—this is NP-complete, resolving a long-standing . The proof relies on a probabilistic reduction from 3-SAT, showing that even in highly structured digraphs like tournaments, finding an optimal linear ordering to minimize backward arcs is intractable. This problem models ordering tasks in social networks, , and scheduling, where acyclic representations are essential. Bandwidth allocation in communication networks, particularly under quadratic cost models that capture interference or capacity constraints, formulates as a quadratic assignment problem variant, which is NP-complete. Such models optimize the assignment of channels or frequencies to minimize total quadratic penalties from overlaps, with hardness inherited from the general quadratic assignment problem via reductions that encode . This arises in and overlay networks, where exact solutions are infeasible for large-scale deployments. Recent advancements have identified NP-complete problems in emerging modeling domains, such as equivalence checking under restricted gate sets, proven NP-complete in 2022 for fixed parameters in circuit mapping tasks that verify functional identity. Similarly, verification of AI models, including checking if a satisfies robustness properties against adversarial inputs, is NP-complete for piecewise-linear activations like ReLU, as shown through reductions from 3-SAT in frameworks. These results underscore the growing intersection of with physical and computational modeling, where classical reductions from satisfiability problems continue to reveal hardness in quantum and contexts.

References

  1. https://dl.acm.org/doi/10.1145/800157.805047
  2. https://www.cs.cornell.edu/courses/cs722/2000sp/karp.pdf
  3. https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf
  4. https://link.springer.com/content/pdf/10.1007/s00153-005-0279-x.pdf
  5. https://theory.cs.princeton.edu/complexity/NPchap.pdf
  6. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
  7. https://dl.acm.org/doi/book/10.5555/574848
  8. https://www.claymath.org/millennium/p-vs-np/
  9. https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf
  10. https://www.preprints.org/manuscript/202507.2057
  11. https://gwern.net/doc/cs/algorithm/2012-johnson.pdf
  12. https://www.cs.purdue.edu/homes/hosking/197/canon/karp.pdf
  13. https://www.sciencedirect.com/science/article/pii/0304397576900591
  14. https://epubs.siam.org/doi/10.1137/0211056
  15. https://dl.acm.org/doi/10.1145/321958.321974
  16. https://doi.org/10.1016/0012-365X(92)90130-8
  17. https://core.ac.uk/download/pdf/81168221.pdf
  18. https://www.sciencedirect.com/science/article/pii/S016750600870743X
  19. https://link.springer.com/article/10.1007/BF02280884
  20. https://dl.acm.org/doi/10.1145/800133.804350
  21. https://hal.science/hal-00683311/document
  22. https://www.cs.cityu.edu.hk/~lwang/research/rehard.pdf
  23. https://arxiv.org/abs/1903.05896
  24. https://arxiv.org/abs/1503.04045
  25. https://www.dmg.tuwien.ac.at/hetzl/teaching/s_vistisen_ss24.pdf
  26. https://jair.org/index.php/jair/article/view/3792
  27. https://www.sciencedirect.com/science/article/pii/S0012365X12003287
  28. https://arxiv.org/abs/1706.06708
  29. http://oldtucs.abo.fi/publications/attachment.php?fname=TR754.pdf
  30. https://erikdemaine.org/papers/InstantInsanity_Ianfest2013/paper.pdf
  31. https://www.shadecoder.com/hi/topics/what-is-backtracking-a-practical-guide-for-2025
  32. https://arxiv.org/abs/2203.14864
  33. https://link.springer.com/chapter/10.1007/978-3-7643-7400-6_5
  34. https://dl.acm.org/doi/10.1145/800113.803627
  35. https://www.karlin.mff.cuni.cz/~barto/Articles/2020_Berg_AAA99.pdf
  36. https://doi.org/10.1089/cmb.1998.5.27
  37. https://www.sciencedirect.com/science/article/pii/S0196677403000476
  38. https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/minimum-feedback-arc-set-problem-is-nphard-for-tournaments/042E28CA7AA5E6555592DEEE671EA3FA
  39. https://www.sciencedirect.com/science/article/abs/pii/S037722179600330X
  40. https://ui.adsabs.harvard.edu/abs/2022QuIP...21..361Z/abstract
  41. https://doi.org/10.1145/3062343.3062363
Add your contribution
Related Hubs
User Avatar
No comments yet.