Feb 19, 2026  
2025-2026 University Catalog 
    
Catalog Navigation
  Catalog Home
  Purdue University In Indianapolis
  Academic Calendar
  Academic Regulations & Student Conduct
  Courses
  Graduate and Undergraduate Programs Lists
  Articulation Agreements and TSAP
  Combined Degree Programs (Purdue Undergraduate/Graduate)
  Undergraduate Requirements
  Undergraduate Outcomes-based Core Curriculum
  Civics Literacy
  Degree in 3
  Academic Colleges
  College of Agriculture
  Daniels School of Business
  College of Education
  College of Engineering
  Exploratory Studies (Undergraduate)
  College of Health and Human Sciences
  Honors College
  College of Liberal Arts
  Libraries and School of Information Studies
  College of Pharmacy
  Polytechnic Institute
  College of Science
  College of Veterinary Medicine
  Joint and Special Programs (Graduate & Undergraduate)
  My Portfolio
HELP
2025-2026 University Catalog
Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Add to Portfolio (opens a new window)

CS 48300 - Introduction To The Theory Of Computation

Credit Hours: 3.00.  Turing machines and the Church-Turing thesis; decidability; halting problem; reducibility; undecidable problems; decidability of logical theories; Kolmogorov complexity; time classes; P, NP, NP-complete; space classes; Savitch’s theorem, PSPACE-completeness, NL-completeness; hierarchy theorems; approximation theorems; probabilistic algorithms; applications of complexity to parallel computation and cryptography.
Credits: 3.00


Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Add to Portfolio (opens a new window)