Psychology Dictionary of Arguments

Home Screenshot Tabelle Begriffe

NP-completeness: NP-completeness is a concept in computational complexity theory. A problem is NP-complete if it is both in NP (meaning that it can be solved in polynomial time by a non-deterministic Turing machine) and NP-hard (meaning that every other problem in NP can be reduced to it in polynomial time). See also Calculability, Complexity, Reducibility, Turing-Machine.
Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments.

Author Concept Summary/Quotes Sources

Peter Norvig on NP-Completeness - Dictionary of Arguments

Norvig I 8
NP-Completeness/Russell/Norvig: How can one recognize an intractable problem? The theory of NP-completeness, pioneered by Steven Cook (1971)(1) and Richard Karp (1972(2)), provides a method. Cook and Karp showed the existence of large classes of canonical combinatorial search and reasoning problems that are NP-complete. Any problem class to which the class of NP-complete problems can be reduced is likely to be intractable. (Although it has not been proved that NP-complete
Norvig I 9
problems are necessarily intractable, most theoreticians believe it.) These results contrast with the optimism with which the popular press greeted the first computers (…).

1. Cook, S. A. (1971). The complexity of theorem proving procedures. In STOC-71, pp. 151–158.
2. Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. E. and Thatcher, J. W.
(Eds.), Complexity of Computer Computations, pp. 85–103. Plenum.

Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments
The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link
> Counter arguments against Norvig
> Counter arguments in relation to NP-Completeness

Authors A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z  

Concepts A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z