Jul 09, 2024  
2023-2024 University Catalog 
    
Catalog Navigation
  Catalog Home
  General Information
  Calendars
  Academic Regulations & Student Conduct
  Courses
  Undergraduate
  Undergraduate Admissions
  Undergraduate Outcomes-based Core Curriculum
  Civics Literacy
  What’s New
  Undergraduate Programs List
  Undergraduate Certificates
  Undergraduate Minors
  Major Change (CODO) Requirements
  Articulation Agreements/Transfer Single Articulation Programs
  Undergraduate Colleges
  College of Agriculture
  School of Business
  College of Education
  College of Engineering
  Exploratory Studies
  College of Health and Human Sciences
  Honors College
  College of Liberal Arts
  Libraries and School of Information Studies
  College of Pharmacy
  Polytechnic Institute
  Polytechnic Statewide
  Office of the Provost
  College of Science
  College of Veterinary Medicine
  Graduate
  Graduate Studies
  Combined Degree Programs (Purdue undergrad/grad)
  Graduate Programs
  Professional
  College of Pharmacy - Professional
  College of Veterinary Medicine - Professional
HELP
2023-2024 University Catalog [ARCHIVED CATALOG]

Facebook this Page (opens a new window)
Tweet this Page (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)