Complexity

Section 3b: Complexity

  1. Turing Machines and Decidability
    1. Deciable, Acceptable and Co-Acceptable Languages
    2. Turing-Completeness
    3. Reducibility
    4. The Halthing Problem and Undecidable Problems
  2. Complexity Classes
    1. Polynomial Reducibility
    2. Time Complexity: P, NP, coNP and EXPTIME
    3. NP-Completeness and NP-Complete Problems