CSCI 4650U – Elements of Theory of Computation

Provides and develops an understanding of which problems are inherently computable and which problems are tractable or feasible. Topics include: Church’s thesis, recursively enumerable sets, Godel’s incompleteness theorem and the relationships of these results to complexity results involving Turing machine models and P vs. NP hardness.
Credit hours: 3
Lecture hours: 3
Prerequisite(s): CSCI 3070U