NP-completeness (under construction)
A problem L is NP-complete if it is in NP and every other problem in NP can be reduced to L. NP-complete problems are therefore the "hardest" problems in NP: if any NP-complete problem has a polynomial time solution, then P = NP. Many widely studied problems are NP-complete, and practically speaking, one might as well give up looking for polynomial time algorithms for such problems.
This concept is still under construction.
This concept has the prerequisites:
- Know what is meant by a polynomial time reduction
- Know the distinction between the terms "in NP," "NP-hard," and "NP-complete"
- Know the statement of Cook's Theorem (that SAT is NP-complete)
- Prove Cook's theorem
- Be able to prove problems NP-complete
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation