Alex's Notes

❯

❯

SAT is NP complete

SAT is NP-complete

Nov 03, 20231 min read

maths

Statement

Cook-Levin Theorem (1971)

The Satisfiability problem is NP-complete.

Proof

This is long.

Graph View

Statement
Proof

Backlinks

Week 10 - NP-completeness
Week 13 - Known NP-complete problems
3-SAT is NP-complete
Max-SAT is NP-hard
Satisfiability problem (SAT problem)
The k-colourings problem is NP-complete

Created with Quartz v4.5.1 © 2025

GitHub
Discord Community