NP-complete
In plain wordsDescribes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all.
Describing a decision problem that is in NP — a proposed solution (certificate) can be verified in polynomial time — and to which every problem in NP can be reduced in polynomial time, so that an efficient algorithm for any one NP-complete problem would yield efficient algorithms for all of NP. A problem is NP-hard if every NP problem reduces to it, whether or not it is itself in NP; finding a shortest traveling-salesman tour is NP-hard. Whether P equals NP is the central open question of theoretical computer science, and most researchers believe it does not. Many AI problems are NP-complete — SATBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., graph coloring, general constraint satisfactionconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes. — and some are harder: exact inference in Bayesian networksBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence. is NP-hard and plan existence in classical planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes. is PSPACE-complete. Hence AI's reliance on heuristicsheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., approximation and exploiting problem structure.
The scheduling problem is NP-complete, so we settled for a local-search heuristic that is usually within 2 percent of optimal.
Origin
Stephen Cook (1971) and Leonid Levin (1973) independently showed that SAT is complete for NP, and Richard Karp (1972) proved 21 classic combinatorial problems complete. Donald Knuth's 1974 poll of colleagues on terminology settled 'NP-hard'; Michael Garey and David Johnson's 1979 book cataloged hundreds of NP-complete problems.
Usage note
Often misused to mean merely 'very hard'. NP stands for 'nondeterministic polynomial time', not 'non-polynomial'. AI-completeAI-complete, adj.: Describes a problem believed to be so hard that solving it would require general, human-level intelligence, such as flawless translation or truly understanding a story. is an informal analogy, not a formal complexity class.
Related
- Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions.
- combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.
- constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- AI-completeAI-complete, adj.: Describes a problem believed to be so hard that solving it would require general, human-level intelligence, such as flawless translation or truly understanding a story.
- AI-completeAI-complete, adj.: Describes a problem believed to be so hard that solving it would require general, human-level intelligence, such as flawless translation or truly understanding a story.
Sources
- Karp, R. M. (1972). Reducibility Among Combinatorial Problems. In Complexity of Computer Computations. Plenum, 85–103.
- Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Mentioned in
AI-completeAI-complete, adj.: Describes a problem believed to be so hard that solving it would require general, human-level intelligence, such as flawless translation or truly understanding a story., Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers., constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., propositional logicpropositional logic, n.: The simplest formal logic: whole statements that are either true or false, joined by 'and', 'or', 'not' and 'if… then', with exact rules for working out whether the combination is true., traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added., integer programminginteger programming, n.: Finding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find.