Apr 27, 2024  
School of Graduate Studies Calendar, 2019-2020 
    
Catalog Navigation
  Calendar Home
  Directory for Information
  Officers of Administration
  Vice-Provost and Dean of Graduate Studies
  Associate Deans of Graduate Studies
  Sessional Dates 2019-2020
  Graduate Study at McMaster University
  General Regulations of the Graduate School
  Regulations for Master’s Degrees
  Regulations for the Doctor of Philosophy Degree
  Financial Matters
  Additional University Regulations Affecting Graduate Students
  General Information
  Graduate Scholarships, Bursaries and Other Awards
  Governing Bodies

  Areas of Study
  DeGroote School of Business
  Faculty of Engineering
  Faculty of Humanities
  Faculty of Health Sciences
  Faculty of Science
  Faculty of Social Sciences
  Interdisciplinary
  Course Listings
  My Favourites
HELP
School of Graduate Studies Calendar, 2019-2020 [-ARCHIVED CALENDAR-]

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

CAS 705 / Computability and Complexity

3 unit(s)

Staff

Computability: Finite automata, Turing machines, and recursive functions. The Halting problem and the Church-Turing thesis. Complexity: Classes defined in terms of time, space, and circuits. The reachability method. The P vs. NP problem, Cook’s theorem, and NP-completeness. The Time and Space Hierarchy theorems. Randomized and parallel computations.


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