7
7.5
8.565
6.1
5.082
6.627
7.9
7.2
Eps:
12
TV Show
8
7.6
6.954
7.476
6.497
List of NP-complete problems GudangMovies21 Rebahinxxi LK21
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
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).
1-planarity
3-dimensional matching: SP1
Bandwidth problem: GT40
Bipartite dimension: GT18
Capacitated minimum spanning tree: ND5
Route inspection problem (also called Chinese postman problem) for mixed graphs (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.: ND25, ND27
Clique cover problem: GT17
Clique problem: GT19
Complete coloring, a.k.a. achromatic number: GT5
Cycle rank
Degree-constrained spanning tree: ND1
Domatic number: GT3
Dominating set, a.k.a. domination number: GT2
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.: ND2
Feedback vertex set: GT7
Feedback arc set: GT8
Graph coloring: GT4
Graph homomorphism problem: GT52
Graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, Hamiltonian subgraphs, forests, perfect matchings) are known NP-complete. Partition into cliques is the same problem as coloring the complement of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.: GT11, GT12, GT13, GT14, GT15, GT16, ND14
Grundy number of a directed graph.: GT56
Hamiltonian completion: GT34
Hamiltonian path problem, directed and undirected.: GT37, GT38, GT39
Induced subgraph isomorphism problem
Graph intersection number: GT59
Longest path problem: ND29
Maximum bipartite subgraph or (especially with weighted edges) maximum cut.: GT25, ND16
Maximum common subgraph isomorphism problem: GT49
Maximum independent set: GT20
Maximum Induced path: GT23
Minimum maximal independent set a.k.a. minimum independent dominating set
NP-complete special cases include the minimum maximal matching problem,: GT10 which is essentially equal to the edge dominating set problem (see above).
Metric dimension of a graph: GT61
Metric k-center
Minimum degree spanning tree
Minimum k-cut
Minimum k-spanning tree
Minor testing (checking whether an input graph
G
{\displaystyle G}
contains an input graph
H
{\displaystyle H}
as a minor); the same holds with topological minors
Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph. (The minimum spanning tree for an entire graph is solvable in polynomial time.)
Modularity maximization
Monochromatic triangle: GT6
Pathwidth, or, equivalently, interval thickness, and vertex separation number
Rank coloring
k-Chinese postman
Shortest total path length spanning tree: ND3
Slope number two testing
Recognizing string graphs
Subgraph isomorphism problem: GT48
Treewidth
Testing whether a tree may be represented as Euclidean minimum spanning tree
Vertex cover: GT1
Mathematical programming
3-partition problem: SP15
Bin packing problem: SR1
Bottleneck traveling salesman: ND24
Uncapacitated facility location problem
Flow Shop Scheduling Problem
Generalized assignment problem
Integer programming. The variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also NP-complete: MP1
Some problems related to Job-shop scheduling
Knapsack problem, quadratic knapsack problem, and several variants: MP9
Some problems related to Multiprocessor scheduling
Numerical 3-dimensional matching: SP16
Open-shop scheduling
Partition problem: SP12
Quadratic assignment problem: ND43
Quadratic programming (NP-hard in some cases, P if convex)
Subset sum problem: SP13
Variations on the Traveling salesman problem. The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.: ND22, ND23
Formal languages and string processing
Closest string
Longest common subsequence problem over multiple sequences: SR10
The bounded variant of the Post correspondence problem: SR11
Shortest common supersequence over multiple sequences: SR8
Extension of the string-to-string correction problem: SR8
Games and puzzles
Bag (Corral)
Battleship
Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself.
Edge-matching puzzles
Fillomino
(Generalized) FreeCell
Goishi Hiroi
Hashiwokakero
Heyawake
(Generalized) Instant Insanity: GP15
Kakuro (Cross Sums)
Kingdomino
Kuromasu (also known as Kurodoko)
LaserTank
Lemmings (with a polynomial time limit)
Light Up
Mahjong solitaire (with looking below tiles)
Masyu
Minesweeper Consistency Problem (but see Scott, Stege, & van Rooij)
Nonograms
Numberlink
Nurikabe
(Generalized) Pandemic
Peg solitaire
n-Queens completion
Optimal solution for the N×N×N Rubik's Cube
SameGame
Shakashaka
Slither Link on a variety of grids
(Generalized) Sudoku
Tatamibari
Tentai Show
Problems related to Tetris
Verbal arithmetic
Other
Berth allocation problem
Betweenness
Assembling an optimal Bitcoin block.
Boolean satisfiability problem (SAT).: LO1 There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals (3SAT), since it is used in the proof of many other NP-completeness results.: p. 48
Circuit satisfiability problem
Conjunctive Boolean query: SR31
Cyclic ordering
Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).: SP2
Finding the global minimum solution of a Hartree-Fock problem
Upward planarity testing
Hospitals-and-residents problem with couples
Knot genus
Latin square completion (the problem of determining if a partially filled square can be completed)
Maximum 2-satisfiability: LO5
Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger
m
×
n
{\displaystyle m\times n}
matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.
Minimal addition chains for sequences. The complexity of minimal addition chains for individual numbers is unknown.
Modal logic S5-Satisfiability
Pancake sorting distance problem for strings
Solubility of two-variable quadratic polynomials over the integers. Given positive integers
A
,
B
,
C
{\displaystyle \textstyle A,B,C}
, decide existence of positive integers
x
,
y
{\displaystyle x,y}
such that
A
x
2
+
B
y
−
C
=
0
{\displaystyle Ax^{2}+By-C=0}
By the same article existence of bounded modular square roots with arbitrarily composite modulus. Given positive integers
A
,
B
,
C
≥
0
{\displaystyle \textstyle A,B,C\geq 0}
, decide existence of an integer
x
∈
[
0
,
C
]
{\displaystyle x\in [0,C]}
such that
x
2
≡
A
mod
B
{\displaystyle x^{2}\equiv A{\bmod {B}}}
. The problem remains NP-complete even if a prime factorization of
B
{\displaystyle B}
is provided.
Serializability of database histories: SR33
Set cover (also called "minimum cover" problem). This is equivalent, by transposing the incidence matrix, to the hitting set problem.: SP5, SP8
Set packing: SP3
Set splitting problem: SP4
Scheduling to minimize weighted completion time
Block Sorting (Sorting by Block Moves)
Sparse approximation
Variations of the Steiner tree problem. Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.: ND13
Three-dimensional Ising model
See also
Existential theory of the reals § Complete problems
Karp's 21 NP-complete problems
List of PSPACE-complete problems
Reduction (complexity)
Notes
References
General
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676.. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047.
Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103.
Dunne, P.E. "An annotated list of selected NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. Retrieved 21 June 2008.
Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 21 June 2008.
Dahlke, K. "NP-complete problems". Math Reference Project. Retrieved 21 June 2008.
Specific problems
Friedman, E (2002). "Pearl puzzles are NP-complete". Stetson University, DeLand, Florida. Archived from the original on 4 September 2006. Retrieved 21 June 2008.
Grigoriev, A; Bodlaender, H L (2007). "Algorithms for graphs embeddable with few crossings per edge". Algorithmica. 49 (1): 1–11. CiteSeerX 10.1.1.61.3576. doi:10.1007/s00453-007-0010-x. MR 2344391. S2CID 8174422.
Hartung, S; Nichterlein, A (2012). "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs". How the World Computes. Lecture Notes in Computer Science. Vol. 7318. Springer, Berlin, Heidelberg. pp. 283–292. CiteSeerX 10.1.1.377.2077. doi:10.1007/978-3-642-30870-3_29. ISBN 978-3-642-30869-7. S2CID 6112925.
Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake" (PDF). Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.
Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:10.1007/BF03025367. S2CID 122435790. Further information available online at Richard Kaye's Minesweeper pages.
Kashiwabara, T.; Fujisawa, T. (1979). "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph". Proceedings. International Symposium on Circuits and Systems. pp. 657–660.
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "One-dimensional logic gate assignment and interval graphs". IEEE Transactions on Circuits and Systems. 26 (9): 675–684. doi:10.1109/TCS.1979.1084695.
Lengauer, Thomas (1981). "Black-white pebbles and graph separation". Acta Informatica. 16 (4): 465–475. doi:10.1007/BF00264496. S2CID 19415148.
Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). "Complexity of finding embeddings in a k-tree". SIAM Journal on Algebraic and Discrete Methods. 8 (2): 277–284. doi:10.1137/0608024.
Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". Proceedings of Third International Conference on Fun with Algorithms (FUN 2004). pp. 65–76.
External links
A compendium of NP optimization problems
Graph of NP-complete Problems
Kata Kunci Pencarian:
list of np complete problemslist of all np complete problems
UCSanDiegoX: NP-Complete Problems | edX
NP Complete Question Series | PDF | Time Complexity | Mathematics
Class NP, NP - Complete, and NP - Hard Problems | PDF | Computational ...
Np Hard and Np Complete Problems
PPT - NP-complete and NP-hard problems PowerPoint Presentation, free ...
NP-complete problems Flashcards | Quizlet
😊 Solving np complete problems. NP. 2019-02-02
NP-Complete Problems
List of NP-Complete problems | Linear Programming | Computational Problems
NP-Complete and NP-Hard Problems - CodeCrucks
List Of Np Complete Problems Pdf
List Of Np Complete Problems Pdf
Search Resultslist of np complete problems
Daftar Isi
List of NP-complete problems - 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 …
A list of useful NP-Complete problems - University of Illinois …
A list of useful NP-Complete problems 1 Satisfiability Circuit Satisfiability Instance: A circuit C with m inputs Question: Is there an input for C such that C returns true for it. Definition 1.1 A …
NP-completeness - Wikipedia
NP-complete problems are in NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can …
Karp's 21 NP-complete problems - Wikipedia
Karp's 21 problems are shown below, many with their original names. The nesting indicates the direction of the reductions used. For example, Knapsack was shown to be NP-complete by …
CS/ECE 374 A (Spring 2024) List of Standard NP-Complete …
Here is a list of known standard NP-complete problems that you may use to reduce from, to prove that new problems are NP-complete. We will provide you this list for the final exam (so, no …
Annotated List of Selected NP-complete Problems - University of …
An Annotated List of Selected NP-complete Problems. The standard textbook on NP-completeness is: Michael Garey and David Johnson: Computers and Intractability - A Guide to …
List of NP-complete problems - Academic Dictionaries and …
Here are some of the more commonly known problems that are NP - complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known …
Introduction to NP-Complete Complexity Classes
May 15, 2024 · NP-complete problems are a subset of the larger class of NP (nondeterministic polynomial time) problems. NP problems are a class of computational problems that can be …
List of NP-complete problems - Wikipedia - BME
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in …
P, NP, CoNP, NP hard and NP complete | Complexity Classes
Oct 3, 2023 · NP-complete problems are the hard problems in NP. Features: NP-complete problems are special as any problem in NP class can be transformed or reduced into NP …
