Study of efficient computation and computational intracability. Time and space complexity; P, NP, and the polynomial-time hierarchy; reductions and completeness; randomized complexity; nonuniform complexity; approximation algorithms and inapproximability. Prerequisite: COSC 4100 or COSC 4200.