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 152 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

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

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

List of NP-complete problems (2,749 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

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

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

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

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

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

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

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

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,886 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 (935 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,777 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].

Induced subgraph (513 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

Complete coloring (613 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

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 (943 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

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

Maximum cut (2,800 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

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

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

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

3-dimensional matching (1,558 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:

Instant Insanity (1,475 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,221 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

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

degree in logic and theoretical computer science (complexity theory and NP-completeness). In 1985 he received his doctorate (Doctorat d'Etat) in mathematics

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

Berman–Hartmanis conjecture (1,234 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,034 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

Complete bipartite graph (959 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

Anna Lubiw (537 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

Boolean satisfiability problem (5,312 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

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 (937 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.

Induced subgraph isomorphism problem (622 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

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.

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

Heterogeneous computing (1,547 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

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

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:

Minesweeper (video game) (1,935 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

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)

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

Quadratic assignment problem (651 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

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

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

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:

Unary numeral system (1,220 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

Graph isomorphism problem (4,069 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

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

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

Connected dominating set (1,222 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):

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

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

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;

Graph isomorphism (1,634 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:

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).

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

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

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

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

Blum–Shub–Smale machine (628 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

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

Minimum routing cost spanning tree (416 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.1: ND3, pg.206. Wu, Bang Ye;

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

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

Graph bandwidth (1,332 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)

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

Pancyclic graph (1,500 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

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 (858 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

List of pioneers in computer science (1,515 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

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:

Quadratic programming (1,902 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

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

Ultimate tic-tac-toe (1,314 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,

Stephen Smale (2,160 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

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,

Set packing (1,518 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

Boxicity (1,515 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

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

Outline of software engineering (2,090 words) [view diff] no match in snippet view article find links to article

some problems are solvable in principle, yet unsolvable in practice NP completeness Computational complexity theory Formal methods Proof of correctness

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

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

Dara Moazzami (1,864 words) [view diff] case mismatch in snippet view article find links to article

two additional books, "Advanced Algorithm: A Guide to the Theory of NP-Completeness" and "Approximation Algorithms." He is also the author of three textbooks

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

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)

Mastermind (board game) (2,501 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,

Łukasiewicz logic (2,415 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

Modular arithmetic (3,934 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. This code uses the C literal notation

Computational complexity (2,976 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:

Exact cover (4,289 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

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

Graph coloring (7,988 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

Multivariate cryptography (1,145 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

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

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

National Resident Matching Program (3,186 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

List of PSPACE-complete problems (1,808 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

Talent scheduling (953 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

Hamiltonian decomposition (1,524 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

Maximum common induced subgraph (722 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)

Galactic algorithm (1,888 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):

Directed acyclic graph (5,628 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:

Turing Award (3,519 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

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

Graph partition (3,345 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

Harvard John A. Paulson School of Engineering and Applied Sciences (3,218 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

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

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):

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:

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

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

Minimum spanning tree (5,421 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:

Metric dimension (graph theory) (2,505 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

Nonogram (4,488 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

Dominating set (4,070 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:

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

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

Halting problem (7,232 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

Tetris (10,239 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

Counter machine (4,601 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

NK model (1,855 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,567 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

Computational chemistry (8,359 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

Turing machine (9,581 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,870 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,690 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,365 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,514 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,266 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:

Quadratic knapsack problem (3,911 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)

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,

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

List of multiple discoveries (10,814 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

Book embedding (8,017 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

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,647 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 University of Michigan alumni (24,232 words) [view diff] exact match in snippet view article find links to article

Stephen A. Cook (A.B. 1961); Turing Award 1982; formalised the notion of NP-completeness in a famous 1971 paper, "The Complexity of Theorem Proving Procedures"

List of Boston University people (12,934 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