Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Strong NP-completeness (view), Weak NP-completeness (view)

searching for NP-completeness 153 found (211 total)

Computers and Intractability (779 words) [view diff] exact match in snippet view article find links to article

Theory of NP-Completeness is a textbook by Michael Garey and David S. Johnson. It was the first book exclusively on the theory of NP-completeness and computational

Richard M. Karp (876 words) [view diff] exact match in snippet view article find links to article

Engineering (1992) for major contributions to the theory and application of NP-completeness, constructing efficient combinatorial algorithms, and applying probabilistic

Michael Garey (177 words) [view diff] exact match in snippet view article find links to article

Johnson) of Computers and Intractability: A Guide to the Theory of NP-completeness. He and Johnson received the 1979 Frederick W. Lanchester Prize from

Degree-constrained spanning tree (374 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5. A2.1: ND1, p. 206.{{citation}}:

Circuit satisfiability problem (1,183 words) [view diff] exact match in snippet view article find links to article

can be reduced to the other satisfiability problems to prove their NP-completeness. The satisfiability of a circuit containing m {\displaystyle m} arbitrary

Karp's 21 NP-complete problems (486 words) [view diff] exact match in snippet view article find links to article

computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem. Karp's 21 problems are shown below, many

List of NP-complete problems (2,746 words) [view diff] exact match in snippet view article find links to article

three literals (3SAT), since it is used in the proof of many other NP-completeness results.: p. 48 Circuit satisfiability problem Conjunctive Boolean

Jaroslav Nešetřil (726 words) [view diff] exact match in snippet view article find links to article

posets (diagram and dimension problems), computer science (complexity, NP-completeness). Nešetřil received his Ph.D. from Charles University in 1973 under

Gadget (computer science) (1,604 words) [view diff] exact match in snippet view article

reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique

Stephen Cook (1,510 words) [view diff] exact match in snippet view article find links to article

notions of polynomial-time reduction (also known as Cook reduction) and NP-completeness, and proved the existence of an NP-complete problem by showing that

Numerical 3-dimensional matching (689 words) [view diff] exact match in snippet view article find links to article

a reduction from 3-dimensional matching via 4-partition. To prove NP-completeness of the numerical 3-dimensional matching, the proof should be similar

Pseudo-polynomial transformation (1,044 words) [view diff] exact match in snippet view article find links to article

subproblem of L 1 {\displaystyle L_{1}} that testifies its strong NP-completeness (i.e. all instances have numerical parameters bounded by a polynomial

Not-all-equal 3-satisfiability (641 words) [view diff] exact match in snippet view article find links to article

variant of the Boolean satisfiability problem, often used in proofs of NP-completeness. Like 3-satisfiability, an instance of the problem consists of a collection

Planar SAT (2,162 words) [view diff] exact match in snippet view article find links to article

NP-complete. Reduction from Planar SAT is a commonly used method in NP-completeness proofs of logic puzzles. Examples of these include Fillomino, Nurikabe

Shared risk resource group (1,883 words) [view diff] exact match in snippet view article find links to article

503.2290. doi:10.1016/j.comnet.2008.04.017. S2CID 1674533. "Proof of NP-completeness of the diverse routing problem with general SRGs (see section 7.1 in

Clique cover (939 words) [view diff] exact match in snippet view article find links to article

reduction that can be used to prove the NP-completeness of the clique cover problem from the known NP-completeness of graph coloring. Perfect graphs are

Schaefer's dichotomy theorem (1,786 words) [view diff] exact match in snippet view article find links to article

theorem. Special cases of Schaefer's dichotomy theorem include the NP-completeness of SAT (the Boolean satisfiability problem) and its two popular variants

Strong duality (259 words) [view diff] no match in snippet view article find links to article

Retrieved October 3, 2011. Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv:1012.5568 [math.OC].

Complete coloring (614 words) [view diff] exact match in snippet view article find links to article

{\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)} approximation ratio. The NP-completeness of the achromatic number problem holds also for some special classes

Induced subgraph (509 words) [view diff] exact match in snippet view article find links to article

4007/annals.2006.164.51, MR 2233847. Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10

Numberlink (522 words) [view diff] exact match in snippet view article find links to article

problem, finding a solution to a given Numberlink puzzle is NP-complete. NP-completeness is maintained even if "zig-zag" paths are allowed. Informally, this

Bottleneck traveling salesman problem (951 words) [view diff] exact match in snippet view article find links to article

Hamiltonian cycle in a graph G with no edge longer than x?", is NP-complete. NP-completeness follows immediately by a reduction from the problem of finding a Hamiltonian

Eugene Lawler (1,211 words) [view diff] exact match in snippet view article find links to article

observe that matroid intersection can be solved in polynomial time. The NP-completeness proofs for two of Karp's 21 NP-complete problems, directed Hamiltonian

Polynomial-time reduction (1,472 words) [view diff] exact match in snippet view article find links to article

21 NP-complete problems MIT OpenCourseWare: 16. Complexity: P, NP, NP-completeness, Reductions Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson

Correlation clustering (1,969 words) [view diff] exact match in snippet view article find links to article

optimal for all of the four objectives. Bansal et al. discuss the NP-completeness proof and also present both a constant factor approximation algorithm

Nurikabe (puzzle) (1,277 words) [view diff] case mismatch in snippet view article

Holzer, Markus; Klein, Andreas; Kutrib, Martin (2004). "On The NP-Completeness of The NURIKABE Pencil Puzzle and Variants Thereof" (PDF). Proceedings

Maximum cut (2,816 words) [view diff] exact match in snippet view article find links to article

yes answer is easy to prove by presenting a large enough cut. The NP-completeness of the problem can be shown, for example, by a reduction from maximum

3-dimensional matching (1,550 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Anna Lubiw (544 words) [view diff] exact match in snippet view article find links to article

single source vertex. Other contributions of Lubiw include proving the NP-completeness of finding permutation patterns, and of finding derangements in permutation

Instant Insanity (1,467 words) [view diff] exact match in snippet view article find links to article

guide to the theory of NP-completeness, W.H. Freeman, p. 258 (problem GP15); Robertson, E.; Munro, I. (1978), "NP-completeness, puzzles, and games", Util

Bandersnatch (2,241 words) [view diff] case mismatch in snippet view article find links to article

S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. In Ashland, OR, USA there is a hiking trail above Lithia Park named

Geometric Folding Algorithms (568 words) [view diff] exact match in snippet view article find links to article

mathematics of paper folding, and mathematical origami. It includes the NP-completeness of testing flat foldability, the problem of map folding (determining

Berman–Hartmanis conjecture (1,250 words) [view diff] exact match in snippet view article find links to article

proof that the nonexistence of sparse NP-complete languages (with NP-completeness defined in the standard way using many-one reductions) is in fact equivalent

Outerplanar graph (2,061 words) [view diff] exact match in snippet view article find links to article

outerplanar graphs may be solved in linear time, in contrast to the NP-completeness of these problems for arbitrary graphs. Every maximal outerplanar graph

Feedback vertex set (1,781 words) [view diff] exact match in snippet view article find links to article

in-degree and out-degree three. Karp's reduction also implies the NP-completeness of the FVS problem on undirected graphs, where the problem stays NP-hard

Complete bipartite graph (960 words) [view diff] case mismatch in snippet view article find links to article

subgraph", Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, p. 196, ISBN 0-7167-1045-5. Diestel 2005, p. 105 Biggs

Edge cover (627 words) [view diff] case mismatch in snippet view article find links to article

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5.

K-edge-connected graph (938 words) [view diff] case mismatch in snippet view article find links to article

1145/234533.234534. M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.

Kurt Mehlhorn (846 words) [view diff] exact match in snippet view article find links to article

Kurt (1984), Data Structures and Algorithms II: Graph Algorithms and NP-completeness, Springer-Verlag. Mehlhorn, Kurt (1984), Data Structures and Algorithms

Induced subgraph isomorphism problem (624 words) [view diff] exact match in snippet view article find links to article

1016/0304-3975(82)90133-5, MR 0644795. Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10

Boolean satisfiability problem (5,387 words) [view diff] exact match in snippet view article find links to article

produced by the Cook–Levin reduction will have 17 satisfying assignments. NP-completeness only refers to the run-time of the worst case instances. Many of the

Monochromatic triangle (481 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5. A1.1: GT6, pg.191. Arnborg

Cut (graph theory) (1,132 words) [view diff] case mismatch in snippet view article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A2.2: ND16, p. 210, ISBN 0-7167-1045-5. Karp, R. M.

Digraph realization problem (493 words) [view diff] exact match in snippet view article find links to article

known as dag realization. Nichterlein & Hartung (2012) proved the NP-completeness of this problem. Berger & Müller-Hannemann (2011) showed that the class

Heterogeneous computing (1,634 words) [view diff] exact match in snippet view article find links to article

Robert, Yves (August 2002). "Partitioning a square into rectangles: NP-completeness and approximation algorithms" (PDF). Algorithmica. 34 (3): 217–239

Bipartite half (493 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

David Plaisted (651 words) [view diff] case mismatch in snippet view article find links to article

Narendran; David A. Plaisted; Wayne Snyder (1990). "Rigid E-Unification: NP-Completeness and Applications to Equational Matings". Inf. Comput. 87 (1/2): 129–95

Unary numeral system (1,251 words) [view diff] exact match in snippet view article find links to article

ISBN 9780199233212. Garey, M. R.; Johnson, D. S. (1978), "'Strong' NP-completeness results: Motivation, examples, and implications", Journal of the ACM

List of mathematical proofs (593 words) [view diff] exact match in snippet view article find links to article

ring commutativity of a boolean ring Boolean satisfiability problem NP-completeness of the Boolean satisfiability problem Cantor's diagonal argument set

Edge dominating set (673 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5. Edge dominating set (decision

Minimum k-cut (847 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1044-8 Saran, H.; Vazirani, V. (1991)

Nondeterministic Turing machine (1,663 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5. Erickson, Jeff. "Nondeterministic

Sartaj Sahni (627 words) [view diff] exact match in snippet view article find links to article

Structures. He has also written highly cited research papers on the NP-completeness of approximately solving certain optimization problems, on open shop

Minesweeper (video game) (2,106 words) [view diff] exact match in snippet view article

original (PDF) on 9 June 2019. — An open-access paper explaining Kaye's NP-completeness result. Richard Kaye's Minesweeper pages Microsoft Minesweeper playable

NP-easy (290 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Graph isomorphism (1,635 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Wayne Snyder (407 words) [view diff] case mismatch in snippet view article find links to article

and David A. Plaisted and Wayne Snyder (1990). "Rigid E-Unification: NP-Completeness and Applications to Equational Matings". Inf. Comput. 87 (1/2): 129–195

Graph isomorphism problem (4,127 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5. Grigor'ev, D. Ju. (1981), "Complexity

Pseudo-polynomial time (876 words) [view diff] case mismatch in snippet view article find links to article

S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. Demaine, Erik. "Algorithmic Lower

Quadratic assignment problem (773 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.5: ND43, pg.218. https://doi

Steiner travelling salesman problem (358 words) [view diff] case mismatch in snippet view article find links to article

S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Huili Zhang, Weitian Tong, Yinfeng

Set splitting problem (526 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. Petrank, Erez (1994).

Barnette's conjecture (1,194 words) [view diff] exact match in snippet view article find links to article

(2000). Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of

Multipartite graph (399 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, ISBN 0-7167-1045-5. Hotho, Andreas; Jäschke, Robert;

Connected dominating set (1,239 words) [view diff] exact match in snippet view article find links to article

1007/s00224-009-9167-9, S2CID 4053586. Douglas, Robert J. (1992), "NP-completeness and degree restricted spanning trees", Discrete Mathematics, 105 (1–3):

Chordal bipartite graph (884 words) [view diff] exact match in snippet view article find links to article

1016/0012-365x(95)00057-4. Müller, Haiko; Brandstädt, Andreas (1987), "The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs", Theoretical

Subcoloring (441 words) [view diff] case mismatch in snippet view article find links to article

Mickael; Ochem, Pascal (2015), "Near-Colorings: Non-Colorable Graphs and NP-Completeness", Electronic Journal of Combinatorics, 22 (1): #P1.57, arXiv:1306.0752

Damm algorithm (1,089 words) [view diff] exact match in snippet view article find links to article

(1): 1–28. ISSN 1561-2848. See page 23. Chen Jiannan (2009). "The NP-completeness of Completing Partial anti-symmetric Latin squares" (PDF). Proceedings

Odd cycle transversal (663 words) [view diff] exact match in snippet view article find links to article

property Π", Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, p. 195 Yannakakis, Mihalis (1978), "Node-and edge-deletion

Blum–Shub–Smale machine (654 words) [view diff] exact match in snippet view article find links to article

"On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines" (PDF). Bulletin of the

Stephen Smale (2,186 words) [view diff] exact match in snippet view article find links to article

"On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines". Bull. Amer. Math. Soc

Sum coloring (536 words) [view diff] exact match in snippet view article find links to article

ISBN 978-3-540-44186-1, MR 2091822 Marx, Dániel (2005), "A short proof of the NP-completeness of minimum sum interval coloring", Operations Research Letters, 33

Complexity and Real Computation (852 words) [view diff] exact match in snippet view article find links to article

of characteristic zero, which are shown from the point of view of NP-completeness within their computational models to all be equivalent to the complex

Domatic number (973 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Linear arboricity (863 words) [view diff] exact match in snippet view article find links to article

(1): 11–16, doi:10.1007/PL00007233, MR 1828624. Péroche, B. (1984), "NP-completeness of some problems of partitioning and covering in graphs", Discrete

NP-equivalent (450 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

List of pioneers in computer science (1,564 words) [view diff] exact match in snippet view article find links to article

instruction scheduling 1967 Cook, Stephen Formalized the notion of NP-completeness, inspiring a great deal of research in computational complexity theory

Quadratic programming (1,914 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP2, pg.245. Gould, Nicholas

Michael Shub (878 words) [view diff] exact match in snippet view article find links to article

"On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines" (PDF). Bulletin of the

Subgraph isomorphism problem (1,847 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5. A1.4: GT48, pg.202. Gröger,

Ultimate tic-tac-toe (1,318 words) [view diff] no match in snippet view article find links to article

Recursion Tic-tac-toe variants Konforti, Nicole; Epstein, Dave. "NP Completeness in Contemporary Board Games".[dead link‍] Whitney, George; Janoski

Graph bandwidth (1,519 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. Gruber, Hermann (2012)

Verbal arithmetic (1,432 words) [view diff] exact match in snippet view article find links to article

Feynman. Basic Books. ISBN 9780786722426. David Eppstein (1987). "On the NP-completeness of cryptarithms" (PDF). SIGACT News. 18 (3): 38–40. doi:10.1145/24658

Matching preclusion (485 words) [view diff] exact match in snippet view article find links to article

A.; Martin, Sébastien; Picouleau, Christophe (March 2012). "On the NP-completeness of the perfect matching free subgraph problem". Theoretical Computer

Boxicity (1,533 words) [view diff] exact match in snippet view article find links to article

"A special planar satisfiability problem and a consequence of its NP–completeness", Discrete Applied Mathematics, 52 (3): 233–252, doi:10.1016/0166-218X(94)90143-0

Set packing (1,514 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A3.1: SP3, pg.221. Vazirani

Induced path (1,486 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. p. 196. Gashler, Michael; Martinez, Tony (2012). "Robust

Pancyclic graph (1,614 words) [view diff] exact match in snippet view article find links to article

Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics, 98 (3): 219–225, doi:10

Minimum routing cost spanning tree (595 words) [view diff] exact match in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman. A2.1: ND3, p. 206. ISBN 978-0-7167-1044-8. Wu, Bang Ye; Lancia

Modular arithmetic (3,603 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0716710447. John L. Berggren. "modular arithmetic"

Circular layout (1,818 words) [view diff] exact match in snippet view article find links to article

Masuda, S.; Kashiwabara, T.; Nakajima, K.; Fujisawa, T. (1987), "On the NP-completeness of a computer network layout problem", Proceedings of the IEEE International

Mastermind (board game) (2,508 words) [view diff] exact match in snippet view article

Retrieved 22 December 2021. De Bondt, Michiel C. (November 2004), NP-completeness of Master Mind and Minesweeper, Radboud University Nijmegen Zhang,

Shortest common supersequence (1,009 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p. 228 A4.2: SR8. ISBN 0-7167-1045-5. Zbl 0411.68039

Matching (graph theory) (2,938 words) [view diff] case mismatch in snippet view article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5. Edge dominating set (decision version)

Łukasiewicz logic (2,455 words) [view diff] no match in snippet view article find links to article

1007/BF00373490 A. Ciabattoni, M. Bongini and F. Montagna, Proof Search and Co-NP Completeness for Many-Valued Logics. Fuzzy Sets and Systems. "Modal Logic: Contemporary

François Lalonde (1,002 words) [view diff] exact match in snippet view article find links to article

theoretical computer science (Computational complexity theory and NP-completeness). In 1985 he received his doctorate in mathematics from the Paris-Saclay

Exact cover (4,328 words) [view diff] exact match in snippet view article find links to article

chessboard have a maximum rather than an exact queen count. Due to its NP-completeness, any problem in NP can be reduced to exact cover problems, which then

Graph coloring (8,095 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 Garey, M. R.; Johnson, D. S.; Stockmeyer

Incidence coloring (3,817 words) [view diff] exact match in snippet view article find links to article

Discrete Mathematics, vol. 309, pp. 3866–3870. Li, X.; Tu, J. (2008), "NP-completeness of 4-incidence colorability of semi-cubic graphs", Discrete Mathematics

Minimum relevant variables in linear system (1,053 words) [view diff] exact match in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman. ISBN 978-0-7167-1044-8. Koehler, Gary J. (November

Multivariate cryptography (1,144 words) [view diff] exact match in snippet view article find links to article

R. (1979). Computers and intractability : a guide to the theory of NP-completeness. Johnson, David S., 1945-. San Francisco: W.H. Freeman. ISBN 0-7167-1044-7

Hamiltonian decomposition (1,522 words) [view diff] exact match in snippet view article find links to article

Mathematics, vol. 3, pp. 259–268, MR 0499124 Péroche, B. (1984), "NP-completeness of some problems of partitioning and covering in graphs", Discrete

Average-case complexity (2,834 words) [view diff] exact match in snippet view article find links to article

to occur polynomially as often in D'. The average-case analogue to NP-completeness is distNP-completeness. A distributional problem (L′, D′) is distNP-complete

National Resident Matching Program (3,192 words) [view diff] no match in snippet view article find links to article

example of a situation with no stable solution and states that proof of NP completeness comes from Ronn 1990. Roth & Peranson 1999, p. 759. Roth & Peranson

Post correspondence problem (2,521 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p. 228. ISBN 0-7167-1045-5. Y. Gurevich (1991). "Average

Post correspondence problem (2,521 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p. 228. ISBN 0-7167-1045-5. Y. Gurevich (1991). "Average

List of PSPACE-complete problems (1,807 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. Eppstein's page on

Computational complexity (2,989 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Galactic algorithm (1,914 words) [view diff] exact match in snippet view article find links to article

424–435. doi:10.1016/j.jctb.2011.07.004. Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2):

Graph partition (2,979 words) [view diff] exact match in snippet view article find links to article

S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. ISBN 978-0-7167-1044-8. Hendrickson, B.; Leland

Maximum common induced subgraph (951 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.4: GT48, pg.202. Kann, Viggo (1992)

Fast syndrome-based hash (2,941 words) [view diff] exact match in snippet view article find links to article

Syndrome decoding is originally a problem from coding theory but its NP-completeness makes it a nice application for cryptography. Regular syndrome decoding

Turing Award (3,534 words) [view diff] exact match in snippet view article find links to article

algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness" University of California, Berkeley 1986 John Hopcroft "For fundamental

Directed acyclic graph (5,647 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences (1st ed.), New York:

Harvard John A. Paulson School of Engineering and Applied Sciences (3,231 words) [view diff] exact match in snippet view article find links to article

PhD '59) - Turing Award winner for contributions to the theory of NP-completeness Iris Mack (PhD '86) - applied mathematician in quantitative finance

Graph minor (4,046 words) [view diff] exact match in snippet view article find links to article

Kawarabayashi, Kobayashi & Reed (2012). Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2):

Random-access stored-program machine (2,620 words) [view diff] case mismatch in snippet view article find links to article

centered around the issues of machine-interpretation of "languages", NP-Completeness, etc. Stephen Kleene (1952), Introduction to Metamathematics, North-Holland

Chordal completion (1,352 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Talent scheduling (972 words) [view diff] case mismatch in snippet view article find links to article

Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif

Rainbow matching (2,561 words) [view diff] case mismatch in snippet view article find links to article

Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif

Optimizing compiler (5,371 words) [view diff] exact match in snippet view article find links to article

"Optimizations in C++ Compilers". ACM Queue. Vol. 17, no. 5. "Lecture 15: NP-completeness, Optimization and Separation" (PDF). IE 511: Integer Programming, Spring

Metric dimension (graph theory) (2,520 words) [view diff] case mismatch in snippet view article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.5: GT61, p. 204. Harary, F.; Melter

Tetris (10,093 words) [view diff] exact match in snippet view article find links to article

problem within a factor of 2 − ε for any constant ε > 0. To prove NP-completeness, it was shown that there is a polynomial reduction between the 3-partition

centered around the issues of machine-interpretation of "languages", NP-Completeness, etc. Calvin Elgot and Abraham Robinson (1964), "Random-Access Stored-Program

Dominating set (4,082 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Nonogram (4,490 words) [view diff] exact match in snippet view article find links to article

Pictopix". Rock, Paper, Shotgun. Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions, vol. TR96-0008, Technical

Slitherlink (2,623 words) [view diff] exact match in snippet view article find links to article

page on Slitherlink Archived 2013-05-22 at the Wayback Machine On the NP-completeness of the Slitherlink Puzzle Archived 2013-01-20 at the Wayback Machine

Halting problem (7,344 words) [view diff] case mismatch in snippet view article find links to article

A book centered around the machine-interpretation of "languages", NP-Completeness, etc. Hodges, Andrew (1983). Alan Turing: the enigma. New York: Simon

Minimum spanning tree (5,460 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Kőnig's theorem (graph theory) (3,433 words) [view diff] exact match in snippet view article

to be computed in polynomial time for bipartite graphs, despite the NP-completeness of these problems for more general graph families. Kőnig's theorem

Computational chemistry (8,349 words) [view diff] exact match in snippet view article find links to article

transforming the two-electron integrals. This proof of NP-hardness or NP-completeness comes from embedding problems like the Ising model into the Hartree-Fock

NK model (1,860 words) [view diff] exact match in snippet view article find links to article

1016/s0022-5193(89)80019-0. PMID 2632988. Weinberger, E. (1996), "NP-completeness of Kauffman's N-k model, a Tuneably Rugged Fitness Landscape", Santa

Linear programming (6,682 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP1: INTEGER PROGRAMMING

Counter machine (4,697 words) [view diff] case mismatch in snippet view article find links to article

centered around the issues of machine-interpretation of "languages", NP-Completeness, etc. Stephen Kleene (1952), Introduction to Metamathematics, North-Holland

Turing machine (9,410 words) [view diff] exact match in snippet view article find links to article

Centered around the issues of machine-interpretation of "languages", NP-completeness, etc. Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001).

Lemmings (video game) (5,769 words) [view diff] exact match in snippet view article

Graham (2004). "The hardness of the Lemmings game, or Oh no, more NP-completeness proofs" (PDF). In Proceedings of the 3rd International Conference on

Polynomial creativity (1,742 words) [view diff] case mismatch in snippet view article find links to article

Berman–Hartmanis conjecture is true. Goldreich, Oded (2010), P, NP, and NP-Completeness: The Basics of Computational Complexity, Cambridge University Press

Steiner tree problem (4,391 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York:

Quadratic residue (5,557 words) [view diff] case mismatch in snippet view article find links to article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 A7.1: AN1, pg.249. Hardy, G. H.;

Random-access machine (7,515 words) [view diff] case mismatch in snippet view article find links to article

centered around the issues of machine-interpretation of "languages", NP-Completeness, etc. Stephen Kleene (1952), Introduction to Metamathematics, North-Holland

Lateral computing (4,212 words) [view diff] no match in snippet view article find links to article

Garey and D. Johnson (1979); Computers and Intractability: A theory of NP Completeness, W.H. Freeman and Company Publishers. M. Sipser (2001); Introduction

Edge coloring (8,472 words) [view diff] exact match in snippet view article find links to article

doi:10.1016/0012-365X(82)90209-6, MR 0676882. Holyer, Ian (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing, 10 (4): 718–720, doi:10

Intersection number (graph theory) (4,270 words) [view diff] case mismatch in snippet view article

S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences (1st ed.), New York:

Book embedding (8,167 words) [view diff] exact match in snippet view article find links to article

the book crossing number of a graph is also NP-hard, because of the NP-completeness of the special case of testing whether the 2-page crossing number is

Quadratic knapsack problem (3,912 words) [view diff] no match in snippet view article find links to article

S. (1979). Computers and intractibility: A guide to the theory of NP completeness. New York: Freeman and Co. Adams, Warren P.; Sherali, Hanif D. (1986)

Stable model semantics (4,921 words) [view diff] exact match in snippet view article find links to article

other words, the set of stable models of a program is an antichain. NP-completeness Testing whether a finite ground logic program has a stable model is

Balanced number partitioning (3,242 words) [view diff] case mismatch in snippet view article find links to article

David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5. Coffman, E. G.; Frederickson,

List of multiple discoveries (11,128 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 978-0-7167-1045-5. Owen Gingerich, "Did Copernicus

Hedonic game (3,880 words) [view diff] exact match in snippet view article find links to article

1016/j.geb.2013.08.006. S2CID 6441501. Ballester, Coralio (Oct 2004). "NP-completeness in hedonic games". Games and Economic Behavior. 49 (1): 1–30. doi:10

Referring expression generation (4,168 words) [view diff] case mismatch in snippet view article find links to article

Johnson (1979). Computers and Intractability: A Guide to the Theory of NP–Completeness. W. H. Freeman, New York. D R Olson (1970). Language and thought: Aspects

Pathwidth (7,684 words) [view diff] exact match in snippet view article find links to article

1016/S0095-8956(03)00037-6. Kashiwabara, T.; Fujisawa, T. (1979), "NP-completeness of the problem of finding a minimum-clique-number interval graph containing

Multiway number partitioning (4,754 words) [view diff] case mismatch in snippet view article find links to article

S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. p. 238. ISBN 978-0716710448. Hochbaum,

List of Boston University people (13,045 words) [view diff] exact match in snippet view article find links to article

executive vice president 1971–1971 Leonid Levin – co-discoverer of NP-completeness Robert J. McShea Adil Najam – dean, Frederick S. Pardee School of Global