NP-Complete Algorithm
(Redirected from NP-complete algorithm)
Jump to navigation
Jump to search
An NP-Complete Algorithm is a computing algorithm that can be implemented by an NP-complete system (to solve NP-complete tasks).
- Context:
- It can (typically) be an Inefficient Algorithm (because an efficient algorithm would imply that an efficient algorithm can solve all NP tasks).
- …
- Counter-Example(s):
- a P Algorithm.
- See: NP-Hard Algorithm.
References
2014
- (Leyton-Brown et al., 2014) ⇒ Kevin Leyton-Brown, Holger H. Hoos, Frank Hutter, and Lin Xu. (2014). “Understanding the Empirical Hardness of NP -complete Problems.” In: Communications of the ACM Journal, 57(5). doi:10.1145/2594413.2594424
- QUOTE: Problems are intractable when they "can be solved, but not fast enough for the solution to be usable."13 NP-complete problems are commonly said to be intractable; however, the reality is more complex. All known algorithms for solving NP-complete problems require exponential time in the worst case; however, these algorithms nevertheless solve many problems of practical importance astoundingly quickly, and are hence relied upon in a broad range of applications.