Dec 06, 2025  
2024-2025 University Catalog 
    
Catalog Navigation
  Catalog Home
  Purdue University In Indianapolis
  Programs Lists
  Degree in 3
  Academic Regulations & Student Conduct
  Undergraduate Admissions
  Undergraduate Outcomes-based Core Curriculum
  Civics Literacy
  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)
  Articulation Agreements and TSAP
  Combined Degree Programs (Purdue Undergraduate/Graduate)
  My Portfolio
HELP
2024-2025 University Catalog [ARCHIVED 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. Typically offered Fall Spring.Credits: 3.00


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