The difference between computable and uncomputable problems and between feasible and infeasible problems. Regarding the latter, what properties of a problem make it computationally simple? What properties of a problem may preclude its having efficient algorithms? How computationally hard are problems? Complete sets and low information content; P=NP?; unambiguous computation, one-way functions, and cryptography; reductions relating the complexity of problems; complexity classes and hierarchies. Students taking this course at the 400 level may be required to complete additional tests, readings, or assignments.
| CRN | Course | Course Title | Term | Credits | Status | ||||
| 29607 | CSC 286 | COMPUTATIONAL COMPLEXITY | Fall 2013 | 4.0 | Open | ||||
| Schedule: | Day | Begin | End | Building | Room | ||||
| MW | 1400 | 1515 | CSB | 632 | |||||
| Enrollment: | Sec Enroll | Sec Cap | Total Enroll | Total Cap | Updated | ||||
| 7 | 999 | 8 | 999 | 11/28/2012 | |||||