The CIM Courses system will be down temporarily undergoing routine maintenance.
May 9, 2017 by Misrak Negatu (misrak)
MATH 3740 : Computational Complexity
Tue, 09 May 2017 08:03:46 GMT
Fri, 05 May 2017 17:25:23 GMT
Catalog Pages referencing this course
Programs referencing this course
Columbian College of Arts and Sciences
Long Course Title
Short Course Title
Number of Credits
Default Grading Method
Repeatable for Credit?
MATH 2971 or MATH 2971W
Frequency of Offering
Are there Course Equivalents?
Are Fees Applicable?
Explanation and Description of Fees
Are Additional Resources Required?
Explanation of Additional Resources
Justification for Additional Resources
Describe any Sources of Additional Funding
Automata and languages; deterministic and nondeterministic Turing machines; space and time complexity measures and classes; P-versus-NP problem; traveling salesman problem and other NP-complete problems; intractability; circuit complexity; introduction to probabilistic and quantum algorithms.
As a result of completing this course students should be able to:
1.Design finite automata, push-down automata, and Turing machines, and relate the languages they accept to Chomsky's hierarchy;
2.Demonstrate that a language is not regular, not context-free, or not decidable;
3.Know various time and space complexity classes and apply complex- ity analysis to specific problems;
4.Analyze polynomial reductions of NP-complete problems;
5.Compare and contrast quantum computing and classical computing.
Uploaded a Course Syllabus
Required Syllabus Template_082516.docx
Explanation of how the course differs from similar GW courses
CCAS - GCR: Q & L
Course Reviewer Comments
Sun, 19 Feb 2017 01:05:01 GMT
Rollback: please include all required elements to your syllabus. template attached for further guidance.