Cook-Levin Theorem

#complexity-theory

Theorem (Cook, Levin)

SAT is NPTIME-complete