List of NP-complete problems and Category talk:Passenger rail transportation in the United States: Difference between pages
(Difference between pages)
Content deleted Content added
m wikilink fixed, this time for real |
m TWP |
||
| Line 1: | Line 1: | ||
{{TrainsWikiProject|class=cat|bycountry=yes|passenger=yes}} |
|||
Here are some of the more commonly known problems that are [[NP-complete]] when expressed as [[decision problem]]s. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book ''Computers and Intractability: A Guide to the Theory of NP-Completeness'', and are here presented in the same order and organization. |
|||
{{Expand list|date=August 2008}} |
|||
== [[Computational geometry]]== |
|||
*[[Minimum weight triangulation]] for a set of points in the plane <ref>[http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cs/0601002 Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)]</ref> |
|||
*Testing whether a [[tree (graph theory)|tree]] may be represented as [[Euclidean minimum spanning tree]] |
|||
*[[Unit disk graph]] recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)<ref>H. Breu and [[David G. Kirkpatrick]]. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998</ref> |
|||
*Many [[motion planning]] among polygonal obstacles in the plane are NP-hard. |
|||
**[[Planar partitioning into connected subassemblies]]: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from A\S by a collision-free rigid motion of S, and such that both S and A\S are connected. <ref>"Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165. </ref> |
|||
== Graph theory == |
|||
=== Covering and partitioning === |
|||
*[[Vertex cover problem|Vertex cover]] |
|||
*[[Dominating set problem|Dominating set]] |
|||
*[[Domatic number problem|Domatic number]] |
|||
*[[Graph coloring|Graph k-colorability]] |
|||
*[[Achromatic number]] |
|||
*[[Grundy number]] |
|||
*[[Monochromatic triangle]] |
|||
*[[Feedback vertex set]] |
|||
*[[Feedback arc set]] |
|||
*[[Partial feedback edge set]] |
|||
*[[Minimum maximal matching]] |
|||
*[[Partition into triangles]] |
|||
*[[Partition into isomorphic subgraphs]] |
|||
*[[Partition into Hamiltonian subgraphs]] |
|||
*[[Partition into forests]] |
|||
*[[Partition into cliques]] |
|||
*[[Partition into perfect matchings]] |
|||
*[[Two-stage maximum weight stochastic matching]] |
|||
*[[Covering by cliques]] |
|||
*[[Berth Allocation Problem (BAP)]] |
|||
*[[Bipartite dimension|Covering by complete bipartite subgraphs]] |
|||
=== Subgraphs and supergraphs === |
|||
*[[Clique problem|Clique]] |
|||
*[[Independent set problem|Independent set]] |
|||
*[[Induced subgraph with property Pi]] |
|||
*[[Induced connected subgraph with property Pi]] |
|||
*[[Induced path]] |
|||
*[[Balanced complete bipartite subgraph]] |
|||
*[[Bipartite subgraph]] |
|||
*[[Degree-bounded connected subgraph]] |
|||
*[[Planar subgraph]] |
|||
*[[Edge-subgraph]] |
|||
*[[Transitive subgraph]] |
|||
*[[Uniconnected subgraph]] |
|||
*[[Minimum k-connected subgraph]] |
|||
*[[Cubic subgraph]] |
|||
*[[Minimum equivalent digraph]] |
|||
*[[Hamiltonian completion]] |
|||
*[[Interval graph completion]] |
|||
*[[Path graph completion]] |
|||
=== Vertex ordering === |
|||
*[[Hamiltonian path problem|Hamiltonian circuit]] |
|||
*[[Directed Hamiltonian circuit problem|Directed Hamiltonian circuit]] |
|||
*[[Hamiltonian path problem|Hamiltonian path]] |
|||
*[[Bandwidth problem|Bandwidth]] |
|||
*[[Directed bandwidth]] |
|||
*[[Optimal linear arrangement]] |
|||
*[[Directed optimal linear arrangement]] |
|||
*[[Minimum cut linear arrangement]] |
|||
*[[Rooted tree arrangement]] |
|||
*[[Directed elimination ordering]] |
|||
*[[Elimination degree sequence]] |
|||
=== Iso- and other morphisms === |
|||
*[[Subgraph isomorphism problem|Subgraph isomorphism]] |
|||
*[[Largest common subgraph]] |
|||
*[[Maximum subgraph matching]] |
|||
*[[Graph contractability]] |
|||
*[[Graph homomorphism]] |
|||
*[[Digraph D-morphism]] |
|||
=== Miscellaneous === |
|||
*[[Path with forbidden pairs]] |
|||
*[[Multiple choice matching]] |
|||
*[[Graph Grundy numbering]] |
|||
*[[Kernel problem|Kernel]] |
|||
*[[K-closure]] |
|||
*[[Intersection graph basis]] |
|||
*[[Path distinguishers]] |
|||
*[[Metric dimension (graph theory)|Metric dimension]] |
|||
*[[Nesetril-Rödl dimension]] |
|||
*[[Threshold number]] |
|||
*[[Oriented diameter]] |
|||
*[[Weighted diameter]] |
|||
== Network design == |
|||
=== Spanning trees === |
|||
*[[Degree-constrained spanning tree]] |
|||
*[[Minimum degree spanning tree]] |
|||
*[[Maximum leaf spanning tree]] |
|||
*[[Shortest total path length spanning tree]] |
|||
*[[Bounded diameter spanning tree]] |
|||
*[[Capacitated spanning tree]] |
|||
*[[Geometric capacitated spanning tree]] |
|||
*[[Optimum communication spanning tree]] |
|||
*[[Isomorphic spanning tree]] |
|||
*[[Kth best spanning tree]] |
|||
*[[Bounded component spanning forest]] |
|||
*[[Multiple choice branching]] |
|||
*[[Steiner tree]] |
|||
*[[Geometric Steiner tree]] |
|||
*[[Cable Trench Problem]] |
|||
*[[Minimum Touching Tree/Minimum Length Corridor]] |
|||
=== Cuts and connectivity === |
|||
*[[Graph partitioning]] |
|||
*[[Acyclic partition]] |
|||
*[[Max weight cut]] |
|||
*[[Minimum cut into bounded sets]] |
|||
*[[Biconnectivity augmentation]] |
|||
*[[Strong connectivity augmentation]] |
|||
*[[Network reliability]] |
|||
*[[Network survivability]] |
|||
*[[Multiway Cut]] |
|||
*[[Minimum k-cut]] |
|||
=== Routing problems === |
|||
*[[Bottleneck traveling salesman]] |
|||
*[[Chinese postman for mixed graphs]] |
|||
*[[Euclidean traveling salesman]] |
|||
*[[K most vital arcs]] |
|||
*[[Kth shortest path]] |
|||
*[[Metric traveling salesman]] |
|||
*[[Longest circuit]] |
|||
*[[Longest path]] |
|||
*[[Prize Collecting Traveling Salesman]] |
|||
*[[Rural Postman]] |
|||
*[[Shortest path in general networks]] |
|||
*[[Shortest weight-constrained path]] |
|||
*[[Stacker-crane]] |
|||
*[[Time constrained traveling salesman feasibility]] |
|||
*[[Traveling salesman problem]] |
|||
*[[Vehicle routing problem]] |
|||
=== Flow problems === |
|||
*[[Minimum edge-cost flow]] |
|||
*[[Integral flow with multipliers]] |
|||
*[[Path constrained network flow]] |
|||
*[[Integral flow with homologous arcs]] |
|||
*[[Integral flow with bundles]] |
|||
*[[Undirected flow with lower bounds]] |
|||
*[[Directed two-commodity integral flow]] |
|||
*[[Undirected two-commodity integral flow]] |
|||
*[[Disjoint connecting paths]] |
|||
*[[Maximum length-bounded disjoint paths]] |
|||
*[[Maximum fixed-length disjoint paths]] |
|||
*[[Unsplittable multicommodity flow]] |
|||
=== Miscellaneous === |
|||
*[[Quadratic assignment problem]] |
|||
*[[Minimizing dummy activities in PERT networks]] |
|||
*[[Constrained triangulation]] |
|||
*[[Intersection graph for segments on a grid]] |
|||
*[[Edge embedding on a grid]] |
|||
*[[Geometric connected dominating set]] |
|||
*[[Minimum broadcast time]] |
|||
*[[Min-max multicenter]] |
|||
*[[Min-sum multicenter]] |
|||
*[[Uncapacitated Facility Location]] |
|||
*[[Metric k-center]] |
|||
== Sets and partitions == |
|||
=== Covering, hitting, and splitting === |
|||
*[[3-dimensional matching]] |
|||
*[[Exact cover]] |
|||
*[[Set packing]] |
|||
*[[Set splitting]] |
|||
*[[Set cover problem|Set cover]] |
|||
*[[Minimum test set]] |
|||
*[[Set basis]] |
|||
*[[Hitting set]] |
|||
*[[Intersection pattern]] |
|||
*[[Comparative containment]] |
|||
*[[3-matroid intersection]] |
|||
=== Weighted set problems === |
|||
*[[Partition problem|Partition]] |
|||
*[[Subset sum problem|Subset sum]] |
|||
*[[Subset product]] |
|||
*[[3-partition]] |
|||
*[[Numerical 3-dimensional matching]] |
|||
*[[Numerical matching with target sums]] |
|||
*[[Expected component sum]] |
|||
*[[Minimum sum of squares]] |
|||
*[[Kth largest subset]] |
|||
*[[Kth largest m-tuple]] |
|||
=== Set partitions === |
|||
*[[Median partition]] |
|||
== Storage and retrieval == |
|||
=== Data storage === |
|||
*[[Bin packing problem|Bin packing]] |
|||
*[[Dynamic storage allocation]] |
|||
*[[Pruned trie space minimization]] |
|||
*[[Expected retrieval cost]] |
|||
*[[Rooted tree storage assignment]] |
|||
*[[Multiple copy file allocation]] |
|||
*[[Capacity assignment]] |
|||
=== Compression and representation === |
|||
*[[Shortest common supersequence]] |
|||
*[[Shortest common superstring]] |
|||
*[[Longest common subsequence problem]] for the case of arbitrary (i.e., not ''a priori'' fixed) number of input sequences even in the case of the binary alphabet |
|||
*[[Bounded post correspondence problem]] |
|||
*[[Hitting string]] |
|||
*[[Sparse matrix compression]] |
|||
*[[Consecutive ones submatrix]] |
|||
*[[Consecutive ones matrix partition]] |
|||
*[[Consecutive ones matrix augmentation]] |
|||
*[[Consecutive block minimization]] |
|||
*[[Consecutive sets]] |
|||
*[[2-dimensional consecutive sets]] |
|||
*[[String-to-string correction]] |
|||
*[[Grouping by swapping]] |
|||
*[[External macro data compression]] |
|||
*[[Internal macro data compression]] |
|||
*[[Regular expression substitution]] |
|||
*[[Rectilinear picture compression]] |
|||
*[[Optimal vector quantization codebook]] |
|||
*[[Minimal grammar-based compression]] |
|||
*[[Adaptive Block-size Compression]] |
|||
=== Database problems === |
|||
*[[Minimum cardinality key]] |
|||
*[[Additional key]] |
|||
*[[Prime attribute name]] |
|||
*[[Boyce-Codd normal form violation]] |
|||
*[[Conjunctive query foldability]] |
|||
*[[Boolean conjunctive query]] |
|||
*[[Tableau equivalence]] |
|||
*[[Serializability]] [[of database histories]] |
|||
*[[Safety of database transaction systems]] |
|||
*[[Consistency of database frequency tables]] |
|||
*[[Safety of file protection systems]] |
|||
== Sequencing and scheduling == |
|||
=== Sequencing on one processor === |
|||
*[[Sequencing with release times and deadlines]] |
|||
*[[Sequencing to minimize Tardy tasks]] |
|||
*[[Sequencing to minimize Tardy weight]] |
|||
*[[Sequencing to minimize weighted completion time]] |
|||
*[[Sequencing to minimize weighted tardiness]] |
|||
*[[Sequencing with deadlines and set-up times]] |
|||
*[[Sequencing to minimize maximum cumulative cost]] |
|||
=== Multiprocessor scheduling === |
|||
*[[Multiprocessor scheduling]] |
|||
*[[Precedence constrained scheduling]] |
|||
*[[Resource constrained scheduling]] |
|||
*[[Scheduling with individual deadlines]] |
|||
*[[Preemptive scheduling]] |
|||
*[[Scheduling to minimize weighted completion time]] |
|||
=== Shop scheduling === |
|||
*[[Open-shop scheduling]] |
|||
*[[Flow-shop scheduling]] |
|||
*[[No-wait flow-shop scheduling]] |
|||
*[[Two-processor flow-shop with bounded buffer]] |
|||
*[[Job-shop scheduling]] |
|||
=== Miscellaneous === |
|||
*[[Timetable design]] |
|||
*[[Staff scheduling]] |
|||
*[[Production planning]] |
|||
*[[Deadlock avoidance]] |
|||
== Mathematical programming == |
|||
[[Integer programming]] |
|||
*[[Linear programming|0-1 Integer programming]] |
|||
*[[Quadratic programming]] (NP-hard in some cases, P when convex) |
|||
*[[Cost-parametric linear programming]] |
|||
*[[Feasible basis extension]] |
|||
*[[Minimum weight solution to linear equations]] |
|||
*[[Open hemisphere]] |
|||
*[[K-relevancy]] |
|||
*[[Traveling salesman polytope non-adjacency]] |
|||
*[[Knapsack problem|Knapsack]] |
|||
*[[Integer knapsack]] |
|||
*[[Continuous multiple choice knapsack]] |
|||
*[[Partially ordered knapsack]] |
|||
*[[Generalized assignment problem]] |
|||
*[[Comparative vector inequalities]] |
|||
*[[Sparse approximation]] |
|||
== Algebra and number theory == |
|||
=== Divisibility problems === |
|||
*[[Quadratic congruences]] |
|||
*[[Simultaneous incongruences]] |
|||
*[[Simultaneous divisibility of linear polynomials]] |
|||
*[[Comparative divisibility]] |
|||
*[[Exponential expression divisibility]] |
|||
*[[Non-divisibility of a product polynomial]] |
|||
*[[Non-trivial greatest common divisor]] |
|||
=== Solvability of equations === |
|||
*[[Quadratic diophantine equations]] |
|||
*[[Algebraic equations over GF2|Algebraic equations over GF[2] ]] |
|||
*[[Root of modulus 1]] |
|||
*[[Number of roots for a product polynomial]] |
|||
*[[Periodic solution recurrence relation]] |
|||
=== Miscellaneous === |
|||
*[[Permanent evaluation]] |
|||
*[[Cosine product integration]] |
|||
*[[Equilibrium point problem|Equilibrium point]] |
|||
*[[Unification with commutative operators]] |
|||
*[[Unification for finitely presented algebras]] |
|||
*[[Integer expression membership]] |
|||
*[[Minimal addition chain]] |
|||
== Games and puzzles == |
|||
[[Alternating hitting set]] |
|||
*[[Alternating maximum weighted matching]] |
|||
*[[Annihilation problem|Annihilation]] |
|||
*[[Battleship (puzzle)|Battleship]] |
|||
*[[Clickomania|Clickomania (SameGame)]] |
|||
*[[Cross Sums]] |
|||
*[[Crossword]] puzzle construction |
|||
*[[FreeCell]] |
|||
*[[Instant Insanity]] |
|||
*[[Light Up]] |
|||
*[[LITS]] |
|||
*[[Mastermind (board game)|Mastermind]] |
|||
*[[Masyu]] |
|||
*[[Minesweeper Consistency Problem]] |
|||
*[[Nurikabe]] |
|||
*[[Nonogram|Paint by numbers (Nonogram)]] |
|||
*[[Rabin game]]s |
|||
*[[Sift (game)|Sift]] |
|||
*[[Slither Link]] |
|||
*[[Square-tiling]] |
|||
*[[Sudoku]] |
|||
*[[Tetris]] |
|||
*[[Variable partition truth assignment]] |
|||
*[[Verbal arithmetic]] |
|||
== Logic == |
|||
=== Propositional logic === |
|||
*[[Satisfiability]] |
|||
*[[Satisfiability#3-satisfiability|3-Satisfiability]] |
|||
*[[Not-all-equal 3SAT]] |
|||
*[[One-in-three 3SAT]] |
|||
*[[Maximum 3-Satisfiability]] |
|||
*[[Generalized satisfiability]] |
|||
*[[Non-tautology]] |
|||
*[[Minimum disjunctive normal form]] |
|||
*Truth-functionally complete connectives |
|||
*[[Planar-3SAT]] |
|||
*[[Monotone-3SAT]] |
|||
=== Miscellaneous === |
|||
*[[Modal logic]] S5-Satisfiability |
|||
*[[Negation-free logic]] |
|||
*Conjunctive satisfiability with functions and inequalities |
|||
*[[Minimum axiom set]] |
|||
*[[First order subsumption]] |
|||
*[[Second order instantiation]] |
|||
== Automata and language theory == |
|||
=== Automata theory === |
|||
*Two-way [[finite state automaton]] non-emptiness |
|||
*[[Quasi-realtime automaton]] acceptance |
|||
*Reduction of incompletely specified automata |
|||
*[[Minimum inferred finite state automaton]] |
|||
=== Formal languages === |
|||
*[[Regular expression]] inequivalence |
|||
*[[Minimum inferred regular expression]] |
|||
*[[Reynolds covering]] for [[context-free grammars]] |
|||
*[[Covering for linear grammars]] |
|||
*Structural inequivalence for [[linear grammars]] |
|||
*[[Regular grammar]] inequivalence |
|||
*Non-[[LR(K)]] context-free grammar |
|||
*[[Etol grammar]] non-emptiness |
|||
*[[Context-free programmed language]] membership |
|||
*[[Quasi-real-time language]] membership |
|||
*[[Etol language]] membership |
|||
*[[Tree transducer language]] membership |
|||
== Program optimization == |
|||
=== Code generation === |
|||
*[[Register sufficiency]] |
|||
*[[Feasible register assignment]] |
|||
*[[Register sufficiency for loops]] |
|||
*[[Code generation on a one-register machine]] |
|||
*[[Code generation with unlimited registers]] |
|||
*[[Code generation for parallel assignments]] |
|||
*[[Code generation with address expressions]] |
|||
*[[Code generation with unfixed variable locations]] |
|||
*[[Ensemble computation]] |
|||
*[[Microcode bit optimization]] |
|||
=== Programs and schemes === |
|||
*[[Inequivalence of programs with arrays]] |
|||
*[[Inequivalence of programs with assignments]] |
|||
*[[Inequivalence of finite memory programs]] |
|||
*[[Inequivalence of loop programs without nesting]] |
|||
*[[Inequivalence of simple functions]] |
|||
*[[Strong inequivalence of Ianov schemes]] |
|||
*[[Strong inequivalence for monadic recursion]] |
|||
*[[Non-containment for free B-schemes]] |
|||
*[[Non-freedom for loop-free program schemes]] |
|||
*[[Programs with formally recursive procedures]] |
|||
== Miscellaneous == |
|||
*[[Cyclic ordering]] |
|||
*[[Non-liveness of free choice Petri nets]] |
|||
*[[Reachability for 1-conservative Petri nets]] |
|||
*[[Finite function generation]] |
|||
*[[Permutation generation]] |
|||
*[[Decoding of linear codes]] |
|||
*[[Shapley-Shubik voting power]] |
|||
*[[Clustering problem|Clustering]] |
|||
*[[Randomization test for matched pairs]] |
|||
*[[Maximum likelihood ranking]] |
|||
*[[Matrix domination]] |
|||
*[[Matrix cover]] |
|||
*[[Simply deviated disjunction]] |
|||
*[[Decision tree problem|Decision tree]] |
|||
*[[Minimum weight and/or graph solution]] |
|||
*[[Fault detection in logic circuits]] |
|||
*[[Fault detection in directed graphs]] |
|||
*[[Fault detection with test points]] |
|||
== See also == |
|||
* [[Karp's 21 NP-complete problems]] |
|||
* [[List of PSPACE-complete problems]] |
|||
== References == |
|||
<references/> |
|||
* {{cite book |
|||
| last = Garey |
|||
| first = M.R. |
|||
| authorlink = Michael Garey |
|||
| coauthors = [[David S. Johnson|Johnson, D.S.]] |
|||
| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] |
|||
| year = 1979 |
|||
| publisher = W.H. Freeman |
|||
| location = New York |
|||
| isbn = 0-7167-1045-5 |
|||
}} This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems. |
|||
* {{cite conference |
|||
| last = Cook |
|||
| first = S.A. |
|||
| authorlink = Stephen A. Cook |
|||
| title = The complexity of theorem proving procedures |
|||
| booktitle = Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York |
|||
| year = 1971 |
|||
| pages = 151–158 |
|||
| url = http://dx.doi.org/10.1145/800157.805047 |
|||
| doi = 10.1145/800157.805047 |
|||
}} |
|||
* {{cite web |
|||
| last = Dunne |
|||
| first = P.E |
|||
| title = An annotated list of selected NP-complete problems |
|||
| publisher = COMP202, Dept. of Computer Science, [[University of Liverpool]] |
|||
| url = http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html |
|||
| accessdate = 2008-06-21 |
|||
}} |
|||
* {{cite web |
|||
| last = Crescenzi |
|||
| first = P. |
|||
| coauthors = Kann, V.; Halldórsson, M.; [[Marek Karpinski|Karpinski, M.]]; Woeginger, G |
|||
| title = A compendium of NP optimization problems |
|||
| publisher = KTH NADA, Stockholm |
|||
| url = http://www.nada.kth.se/~viggo/problemlist/compendium.html |
|||
| accessdate = 2008-06-21 |
|||
}} |
|||
* {{cite web |
|||
| last = Dahlke |
|||
| first = K |
|||
| title = NP-complete problems |
|||
| work = Math Reference Project |
|||
| url = http://www.mathreference.com/lan-cx-np,intro.html |
|||
| accessdate = 2008-06-21 |
|||
}} |
|||
* {{cite web |
|||
| first = E |
|||
| last = Friedman |
|||
| title = Pearl puzzles are NP-complete |
|||
| year = 2002 |
|||
| publisher = Stetson University, DeLand, Florida |
|||
| url = http://www.stetson.edu/~efriedma/papers/pearl/pearl.html |
|||
| accessdate = 2008-06-21 |
|||
}} |
|||
[[Category:Mathematics-related lists|NP-complete problems]] |
|||
[[Category:NP-complete problems|*]] |
|||
[[fr:Liste de problèmes NP-complets]] |
|||
[[pl:Lista problemów NP-zupełnych]] |
|||
Revision as of 21:08, 10 October 2008
 | Trains: By country series / Passenger trains Category‑class | |||||||||||||||||||||
| ||||||||||||||||||||||
