# NP-completeness (under construction)

## Summary

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.

## Notes

This concept is still under construction.

## Context

This concept has the prerequisites:

- NP complexity class (NP-complete problems are the hardest problems in NP.)
- propositional satisfiability (SAT is the canonical NP-complete problem.)
- nondeterministic Turing machines (Cook's Theorem is proved by defining nondeterministic Turing machines through SAT clauses.)

## Goals

- 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

## See also

-No Additional Notes-