3. Key Concepts

Key Concepts:

  1. Turing Completeness:
    • A system is Turing complete if it can simulate a Turing machine.
    • Examples: Modern programming languages (e.g., Python, Java).
  2. Decidability:
    • A problem is decidable if an algorithm exists to solve it in finite time.
    • Example: Checking if a number is prime.
  3. Undecidability:
    • A problem is undecidable if no algorithm can solve it for all cases.
    • Example: The Halting Problem (determining whether a program will terminate).
  4. Reduction:
    • A method to prove undecidability by reducing one problem to another.
    • Example: Reducing the Halting Problem to the Post Correspondence Problem.

Complexity Theory

Complexity theory classifies problems based on the resources (time and space) required to solve them.

Key Concepts:

  1. Time Complexity:
    • Measures the number of steps an algorithm takes as a function of input size.
    • Example: O(n), O(n²), O(log n).
  2. Space Complexity:
    • Measures the amount of memory an algorithm uses as a function of input size.
    • Example: O(1), O(n).
  3. Complexity Classes:
    • P: Problems solvable in polynomial time by a deterministic Turing machine.
    • NP: Problems solvable in polynomial time by a non-deterministic Turing machine.
    • NP-Complete: The hardest problems in NP; solving one would solve all NP problems.
    • NP-Hard: Problems at least as hard as NP-Complete problems.
  4. P vs. NP Problem:
    • The most famous unsolved problem in computer science: Is P = NP?