Nondeterministic Time
Overview
Lectures will continue by introducing nondeterministic Turing machines, as well as “verification”, in order to give a definition of nondeterministic time, and associated computational complexity classes.
While properties of nondeterministic time-complexity classes will be discussed, the focus will be on the use of reductions to better understand the relationship between deterministic time-bounded computation and nondeterministic time-bounded computation. This course will review — and, almost certainly, expand on the information about — the theory of NP-completeness, which students have generally seen before when completing CPSC 413.
