BeginnerTopic 33 of 104Software & Computing
NP-completeness
A class of problems with no known polynomial algorithms; P vs NP is unsolved.
In depth
P problems are solvable in polynomial time; NP problems have solutions verifiable in polynomial time; NP-complete problems are the hardest in NP — if one has a polynomial algorithm, all do. Examples: SAT, travelling salesman (decision), subset sum, graph colouring. Practical approaches: approximation, heuristics and special cases.
Key points
- Reductions
- P vs NP is a Millennium Problem
- NP-hard
ExampleOptimising delivery routes for 1000 stops is NP-hard, so heuristics are used.
What is NP-completeness?
A class of problems with no known polynomial algorithms; P vs NP is unsolved.
Why is it important to understand NP-completeness?
NP-completeness tells you when a problem is probably hard, so you can choose heuristics or approximations rather than searching for an exact fast method.
What does NP-complete mean?
A problem is in NP, so solutions can be checked quickly, and it is as hard as any problem in NP, so a fast exact algorithm would solve all of them.
Is P equal to NP?
That is unknown. It is one of the most important open questions in computer science, and most experts expect that P is not equal to NP.
How is NP-completeness used in practice?
Typical applications include scheduling jobs on machines to minimise the finish time where exact solutions are too slow, choosing a travelling salesman route for a delivery van with many stops and packing items into containers with approximation algorithms.
What should I learn before NP-completeness?
Study "Backtracking" first (topic 32 of 104 in Software & Computing). It covers the groundwork this topic builds on.
What are the key points of NP-completeness?
Reductions. P vs NP is a Millennium Problem. NP-hard.
Can you give an example of NP-completeness?
Optimising delivery routes for 1000 stops is NP-hard, so heuristics are used.
What comes after NP-completeness?
The next topic is "Object-oriented programming", which builds directly on this one.
How difficult is NP-completeness?
It is classed as Beginner in Software & Computing (topic 33 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.