CSE department

CSE 200. Computability and Complexity (4 units)

Link to catalog page: https://catalog.ucsd.edu/courses/CSE.html#cse200

Description

Computability review, including halting problem, decidable sets, r.e. sets, many-one reductions; TIME(t(n)), SPACE(s(n)) and general relations between these classes; L, P, PSPACE, NP; NP—completeness; hierarchy theorems; RP, BPP. Prerequisites: CSE 105 or equivalent.

Prerequisite courses

Successor courses

CSE 200 is a prerequisite of the following 4 courses:

• CSE 205A
• CSE 206A
• CSE 208
• CSE 233