List of NP-complete problems 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 no way comprehensive. Many problems of this type can be found in.Graphs and hypergraphs occur frequently in everyday applications. Examples include biological or social networks , which contain hundreds, thousands and even billions of nodes in some cases. 1-planarity 3-dimensional matching Bipartite dimension Capacitated minimum spanning tree Route inspection problem for mixed graphs. The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem. Clique problem Complete coloring , a.k.a. achromatic number Domatic number Dominating set, a.k.a. domination number Bandwidth problem Clique cover problem Rank coloring a.k.a. cycle rank Degree-constrained spanning tree Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets. Feedback vertex set Feedback arc set Graph homomorphism problem Graph coloring Graph partition into subgraphs of specific types 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. Hamiltonian completion Hamiltonian path problem, directed and undirected. Longest path problem Maximum bipartite subgraph or maximum cut . Maximum independent set Maximum Induced path Graph intersection number Metric dimension of a graph Minimum k-cut Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph. Modularity maximization Pathwidth Set cover This is equivalent, by transposing the incidence matrix , to the hitting set problem . Set splitting problem Shortest total path length spanning tree Slope number two testing Treewidth Vertex coverMathematical programming 3-partition problem Bin packing problem Knapsack problem, quadratic knapsack problem , and several variants 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 Euclidean metric. Bottleneck traveling salesman 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 Latin squares Numerical 3-dimensional matching Partition problem Quadratic assignment problem Solving two-variable quadratic polynomials over the integers. Given positive integers, find positive integers such that Quadratic programming Subset sum problem Closest string Longest common subsequence problem over multiple sequences The bounded variant of the Post correspondence problem Shortest common supersequence String-to-string correction problemGames and puzzles Battleship Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself. Eternity II FreeCell Fillomino Hashiwokakero Heyawake Instant Insanity Kakuro Kingdomino Kuromasu LaserTank Lemmings Light Up Masyu Minesweeper Consistency Problem Nimber of a directed graph. Numberlink Nonograms Nurikabe NxNxN Rubik's Cube Pandemic SameGame Set Slither Link on a variety of grids Sudoku Problems related to Tetris Verbal arithmeticOther Berth allocation problem Betweenness Assembling an optimal Bitcoin block. Boolean satisfiability problem. There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals, since it is used in the proof of many other NP-completeness results. Conjunctive Boolean query Cyclic ordering Circuit satisfiability problem Uncapacitated facility location problem Flow Shop Scheduling Problem Generalized assignment problem Upward planarity testing Hospitals-and-residents problem with couples Some problems related to Job-shop scheduling Monochromatic triangle Minimum maximal independent set a.k.a. minimum independent dominating set Maximum common subgraph isomorphism problem Minimum degree spanning tree Minimum k-spanning tree Metric k-center Maximum 2-Satisfiability Modal logic S5-Satisfiability Some problems related to Multiprocessor scheduling Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger m x 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. Non-linear univariate polynomials over GF, n the length of the input. Indeed, over any GF. Open-shop scheduling Pathwidth, or, equivalently, interval thickness , and vertex separation number Pancake sorting distance problem for strings k-Chinese postman Subgraph isomorphism problem Variations of the Steiner tree problem . Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the Euclidean metric. Set packing Serializability of database histories Scheduling to minimize weighted completion time Sparse approximation Block Sorting Second order instantiation Treewidth Testing whether a tree may be represented as Euclidean minimum spanning tree Three-dimensional Ising model Vehicle routing problem
Popular articles Javier Milei - Argentine libertarian economist, author, radio conductor and public speaker sympathetic to the Austrian School of economic thought. He became widely known for his regular ...Jimmy Carter - American politician, philanthropist, and former farmer who served as the 39th president of the United States from 1977 to 1981. A member of the Democratic Party, he previ...UEFA Euro 2024 - The 2024 UEFA European Football Championship , commonly referred to as UEFA Euro 2024 or simply Euro 2024 , will be the 17th edition of the UEFA European Championship, the quadrennial internationa...Argentina - country located mostly in the southern half of South America. Sharing the bulk of the Southern Cone with Chile to the west, the country is also b...Sam Altman - American entrepreneur, investor, programmer, and blogger. He is the former president of Y Combinator and now the CEO of OpenAI. Early life and education. ...Rosalynn Carter - American who served as First Lady of the United States from 1977 to 1981 as the wife of President Jimmy Carter. For decades, she has been a leading advocate for numerou...Next Argentine presidential election - Next Argentine presidential election - presidential election in Argentina....Popular movies The Hunger Games (film) - 2012 American dystopian action thriller science fiction-adventure film directed by Gary Ross and based on Suzanne Collins’s 2008 novel of the same name. It is the first insta...untitled Captain Marvel sequel - part of Marvel Cinematic Universe....Killers of the Flower Moon (film project) - Killers of the Flower Moon - film project in United States of America. It was presented as drama, detective fiction, thriller. The film project starred Leonardo Dicaprio, Robert De Niro. Director of...Five Nights at Freddy's (film) - Five Nights at Freddy's - film published in 2017 in United States of America. Scenarist of the film - Scott Cawthon....Popular video games Minecraft - sandbox video game developed by Mojang Studios. Created by Markus "Notch" Persson in the Java programming language and released as a public alpha for personal computers in 2...Grand Theft Auto V - 2013 action-adventure game developed by Rockstar North and published by Rockstar Games. It is the first main entry in the Grand Theft Auto series since 2008's Grand Theft ...Roblox - online game platform and game creation system that allows users to program games and play games created by other users. Founded by David Baszucki and Erik Cassel in 2004 and released in...Baldur's Gate III - upcoming role-playing video game developed and published by Larian Studios for Microsoft Windows and the Stadia streaming service. It is the third main game in the Baldur's ...Alan Wake - action-adventure video game developed by Remedy Entertainment and published by Microsoft Studios, released for the Xbox 360 and Microsoft Windows. The story follows best-selling thri...Fortnite - online video game developed by Epic Games and released in 2017. It is available in three distinct game mode versions that otherwise share the same general gameplay and game engine: ...Super Mario RPG - is a role-playing video game developed by Square and published by Nintendo for the Super Nintendo Entertainment System in 1996. It was directed by Yoshihiko Maekawa and Chihiro Fujioka and produced by...Popular books Book of Revelation - The Book of Revelation is the final book of the New Testament, and consequently is also the final book of the Christian Bible. Its title is derived from the first word of the Koine Greek text: apok...Book of Genesis - account of the creation of the world, the early history of humanity, Israel's ancestors and the origins...Gospel of Matthew - The Gospel According to Matthew is the first book of the New Testament and one of the three synoptic gospels. It tells how Israel's Messiah, rejected and executed in Israel, pronounces judgement on ...Michelin Guide - Michelin Guides are a series of guide books published by the French tyre company Michelin for more than a century. The term normally refers to the annually published Michelin Red Guide , the oldest...Psalms - The Book of Psalms , commonly referred to simply as Psalms , the Psalter or "the Psalms", is the first book of the Ketuvim , the third section of the Hebrew Bible, and thus a book of th...Ecclesiastes - Ecclesiastes is one of 24 books of the Tanakh , where it is classified as one of the Ketuvim . Originally written c. 450–200 BCE, it is also among the canonical Wisdom literature of the Old Tes...The 48 Laws of Power - non-fiction book by American author Robert Greene. The book...Popular television series The Crown (TV series) - historical drama web television series about the reign of Queen Elizabeth II, created and principally written by Peter Morgan, and produced by Left Bank Pictures and Sony Pictures Tel...Friends - American sitcom television series, created by David Crane and Marta Kauffman, which aired on NBC from September 22, 1994, to May 6, 2004, lasting ten seasons. With an ensemble cast sta...Young Sheldon - spin-off prequel to The Big Bang Theory and begins with the character Sheldon...Modern Family - American television mockumentary family sitcom created by Christopher Lloyd and Steven Levitan for the American Broadcasting Company. It ran for eleven seasons, from September 23...Loki (TV series) - upcoming American web television miniseries created for Disney+ by Michael Waldron, based on the Marvel Comics character of the same name. It is set in the Marvel Cinematic Universe, shar...Game of Thrones - American fantasy drama television series created by David Benioff and D. B. Weiss for HBO. It...Shameless (American TV series) - American comedy-drama television series developed by John Wells which debuted on Showtime on January 9, 2011. It...
OWIKI.org . Text is available under the Creative Commons Attribution-ShareAlike License.