Lecture 24 (Complexity Hierarchy), 12/4/17

Concepts, definitions (in italics):

·         co-NP – class of problems whose complements are in NP (example: PRIMES)

·         EXPTIME = U TIME(2nk) (p. 298)

·         NP, co-NP are subsets of EXPTIME

·         Final complexity picture (3 possible ways)

Reading:

Skills:

Notes: