NP-Complete Decision Task
An NP-Complete Decision Task is an NP decision task X for which it is possible to reduce any other NP problem Y to X in polynomial time (if we can solve Y quickly if we know how to solve X quickly).
- AKA: Nondeterministic Polynomial Time-Complete.
- Context:
- It can be solved by an NP-Complete System (that implements an NP-complete algorithm).
- It can range from being a Non-NP-Hard NP-Complete Task to being an NP-Hard Task.
- Example(s):
- a 3-SAT Task and a Maximum 2-Satisfiability Task.
- a 3-Coloring Task.
- a Partition into Triangles Task.
- a Hamiltonian Path Search Task.
- an NP-Hard Problem, such as traveling salesman problem.
- …
- Counter-Example(s):
- See: P vs. NP, Approximation Algorithm, Computational Complexity Theory, Decision Problem, NP (Complexity), NP-Hard, Nondeterministic Algorithm, Polynomial Time.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/NP-complete Retrieved:2015-9-17.
- In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to “nondeterministic polynomial time”.
Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.
While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms.
- In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to “nondeterministic polynomial time”.
2013
- (Fomin & Kaski, 2013) ⇒ Fedor V. Fomin, and Petteri Kaski. (2013). “Exact Exponential Algorithms.” In: Communications of the ACM Journal, 56(3). doi:10.1145/2428556.2428575
- Many computational problems have been shown to be intractable, either in the strong sense that no algorithm exists at all — the canonical example being the undecidability of the Halting Problem — or that no efficient algorithm exists. From a theoretical perspective perhaps the most intriguing case occurs with the family of NP-complete problems, for which it is not known whether the problems are intractable. That is, despite extensive research, neither is an efficient algorithm known, nor has the existence of one been rigorously ruled out.[16]
To cope with intractability, advanced techniques such as parameterized algorithms [10,13,31] (that isolate the exponential complexity to a specific structural parameter of a problem instance) and approximation algorithms [34] (that produce a solution whose value is guaranteed to be within a known factor of the value of an optimum solution) have been developed. But what can we say about finding exact solutions of non-parameterized instances of intractable problems? At first glance, the general case of an NP-complete problem is a formidable opponent: when faced with a problem whose instances can express arbitrary nondeterministic computation, how is one to proceed at solving a given instance, apart from the obvious exhaustive search that "tries out all the possibilities"?
- Many computational problems have been shown to be intractable, either in the strong sense that no algorithm exists at all — the canonical example being the undecidability of the Halting Problem — or that no efficient algorithm exists. From a theoretical perspective perhaps the most intriguing case occurs with the family of NP-complete problems, for which it is not known whether the problems are intractable. That is, despite extensive research, neither is an efficient algorithm known, nor has the existence of one been rigorously ruled out.[16]
2011
- (Sammut & Webb, 2011) ⇒ Claude Sammut, and Geoffrey I. Webb. (2011). “NP-Completeness.” In: (Sammut & Webb, 2011) p.731
- QUOTE: A decision problem consists in identifying symbol strings, presented as inputs, that have some specified property. The output consists in a yes/no or 0/1 answer. A decision problem belongs to the class P if there exists an algorithm, that is, a deterministic procedure, for deciding any instance of the problem in a length of time bounded by a polynomial function of the length of the input.
A decision problem is in the class NP if it is possible for every yes-instance of the problem to verify in polynomial time, after having been supplied with a polynomial-length witness, that the instance is indeed of the desired property.
An example is the problem to answer the question for two given numbers n and m whether n has a divisor d strictly between m and n. This problem is in NP: if the answer is positive, then such a divisor d will be a witness, since it can be easily checked that d lies between the required bounds, and that n is indeed divisible by d. ...
- QUOTE: A decision problem consists in identifying symbol strings, presented as inputs, that have some specified property. The output consists in a yes/no or 0/1 answer. A decision problem belongs to the class P if there exists an algorithm, that is, a deterministic procedure, for deciding any instance of the problem in a length of time bounded by a polynomial function of the length of the input.
2009
- (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The status of the P versus NP problem.” In: Communications of the ACM, 52(9).
- So P = NP means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well.
We call the very hardest NP problems (which include Partition into Triangles, Clique, Hamiltonian Cycle and 3-Coloring) "NP-complete," that is, given an efficient algorithm for one of them, we can find an efficient algorithm for all of them and in fact any problem in NP. Steve Cook, Leonid Levin, and Richard Karp10, 24, 27 developed the initial theory of NP-completeness that generated multiple ACM Turing Awards.
- So P = NP means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well.
2005
- (Fomin & Kaski, 2013) ⇒ Fedor V. Fomin, and Petteri Kaski. (2013). “Exact Exponential Algorithms.” In: Communications of the ACM Journal, 56(3). doi:10.1145/2428556.2428575
- QUOTE: The three problems we discuss in more detail are Maximum 2-Satisfiability, Graph Coloring, and Hamiltonian Path.