NP-completeness is a classification for decision problems that are the hardest problems in the complexity class NP: their proposed solutions can be verified quickly, in polynomial time, and every other problem in NP can be reduced to them in polynomial time. Despite easy verifiability, no polynomial time algorithm is known for actually solving NP-complete problems, making them a central benchmark of computational hardness. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Disputed
Core PrincipleIf any single NP-complete problem could be solved in polynomial time, every problem in NP could be, which is the substance of the unresolved P versus NP question. 1 Whether P equals NP is one of the seven Millennium Prize Problems and remains unresolved; no known polynomial-time algorithm exists for any NP-complete problem, but this has not been proven impossible. FAQs
Can NP-complete problems be solved in practice?
They are often handled with heuristic methods and approximation algorithms.
A method for computing the solutions to NP-complete problems quickly remains undiscovered, yet computer scientists and programmers still frequently encounter them. In practice NP-complete problems are often addressed by using heuristic methods and approximation algorithms.
Connections
Associated With
P versus NP, Concepts If any NP-complete problem were shown to have a polynomial-time algorithm, every problem in NP would; this is the tightest known link between the two open questions.
Source Wikipedia: NP-completeness
In Field
Source Wikipedia: NP-completeness
Sources
1. Wikipedia: NP-completeness
Wikimedia FoundationIntroduction section
NP-complete problems are the hardest of the problems to which solutions can be verified quickly.
History section, Cook-Levin theorem
The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete, establishing for the first time that such problems do exist.
Lead paragraph
In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly.
- In Field: Algorithms and Complexity Theory
- Associated With: P versus NP
In Group: Polynomial and Nondeterministic Time Classes, Lead
In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.