Skip to main content

Catalog Search

Search Options

Contents

About
Our History and Mission
Accreditation
Academic Integrity
Student Life
Undergraduate Education
Graduate Education
Tuition, Fees and Other Expenses for Undergraduate Students
Tuition, Fees and Other Expenses for Graduate Students
Financing a Stevens Education
School of Business
College of Arts and Letters
Schaefer School of Engineering and Science
Department of Biomedical Engineering
Department of Chemistry and Chemical Biology
Department of Chemical Engineering and Materials Science
Department of Civil, Environmental, and Ocean Engineering
Department of Computer Science
Department of Electrical and Computer Engineering
Department of Mathematical Sciences
Department of Mechanical Engineering
Department of Physics
School of Systems and Enterprises (SSE)
Courses
- AAI - Applied Artificial Intelligence
- ACC - Accounting
- BIA - Business Intelligence and Analytics
- BIO - Biology
- BIOE - Bioengineering
- BME - Biomedical Engineering
- BT - Business and Technology
- CAL-College-of-Arts-Letters
- CE - Civil Engineering
- CH - Chemistry
- CHE - Chemical Engineering
- CLK - Clark Scholars
- CM - Construction Management
- COMM - Professional Communications
- CPE - Computer Engineering
- CS - Computer Science
- DE - Developmental English
- DS - Data Science
- ECON Economics
- EE - Electrical Engineering
- ELC - English Language and Communication
- EM - Engineering Management
- EMT - Executive Management of Technology
- EN - Environmental Engineering
- ENGR - Interdepartmental Engineering
- ES - Enterprise Systems
- FA - Financial Analytics
- FE - Financial Engineering
- FIN - Finance
- GEN - General Elective
- HAR - Humanities/Art
- HHS - Humanities/History
- HLI - Humanities/Literature
- HMU - Humanities/Music
- HONR - Honor Program
- HPL - Humanities/Philosophy
- HSS - Humanities/Social Sciences
- HST - Humanities Science and Technology Studies
- HTH - Humanities/Theater
- HUM - Humanities General
- IDE-Innovation-Design-and-Entrepreneurship
- IPD - Integrated Product Development
- ISE - Industrial and Systems Engineering
- LCH - Language Chinese
- LFR - Language French
- LSP - Language Spanish
- MA - Mathematics
  - 100
  - 200
  - 300
  - 400
  - 500
  - 600
  - 700
  - 800
  - 90
  - 900
- ME - Mechanical Engineering
- MGT - Management
- MIS - Information Systems
- MT - Materials Engineering
- NANO - Nanotechnology
- NE - Naval Engineering
- NIS - Networked Information Systems
- OE - Ocean Engineering
- PAE - Product Architecture and Engineering
- PEP-Physics-Engineering-Physics
- PIN - Pinnacle Scholar
- PME - Pharmaceutical Manufacturing
- QF - Quantitative Finance
- SEF-Science-Engineering-Found-for-Edu
- SES - Systems Engineering Security
- SM - Sustainability Management
- SOC - Service Oriented Computing
- SSW - Software Engineering
- SYS - Systems Engineering
- TE Technical Elective
- TG - Technogenesis
- TM - Telecommunications Management

Catalog Links

Print this page

MA 526 Foundations of computation and computational complexity

The goal of this course is to formalize and analyze algorithms in a mathematically rigorous fashion. The course begins with Turing machines (the standard model of computation) and uses them to answer some fundamental questions in computer science and mathematics:, e.g., mathematical truth is undecidable. After that notions offeasibility are introduced and studied, culminating with the famous P vs NP question. Finally there is an introduction to quantum computation.

Credits

3

Distribution

Pure and Applied Mathematics Program

Offered

Fall Semester