跳到主要内容

8 Theoretical Computer Science

Core Idea of TCS​

  • Goal: Study the fundamental power and limits of computation using formal models.
  • Key features:
    • Abstraction
    • Mathematical rigor
    • Independence from implementation details
  • Central questions:
    • What problems are computable?
    • What problems are efficiently computable?
    • Why are some problems inherently hard?

Models of Computation​

  • Turing Machines: Classical, universal model of computation.
  • Boolean Circuits: Emphasize parallelism (size, depth).
  • Randomized Models: Computation with randomness (e.g., BPP).
  • Quantum Models: Quantum circuits and algorithms (e.g., Shor’s, Grover’s).

Purpose: compare the computational power of different models.

Algorithms and Complexity Theory​

Algorithm Design​

  • Objective: design algorithms that are correct and efficient.
  • Typical problems: sorting, searching, shortest paths, matching.

Complexity Measures​

  • Time complexity and space complexity.
  • Important classes:
    • P: efficiently solvable problems
    • PSPACE, EXP, NEXP: problems requiring more resources

NP-Completeness​

  • NP: problems whose solutions can be verified in polynomial time.
  • NP-complete: the hardest problems in NP.
  • Key implication:
    • If any NP-complete problem is in P, then P = NP.
  • Main technique: polynomial-time many-one reductions.

Explains why many practical problems appear hard.

Reductions​

  • Many-one reduction:
    • Transform problem A to problem B efficiently.
    • Preserve YES/NO answers.
  • Uses:
    • Proving NP-completeness
    • Comparing relative difficulty of problems

One of the most important tools in TCS.

Interactive Proofs​

  • Model: interaction between a Prover and a Verifier.
  • Key results:
    • IP = PSPACE
    • MIP = NEXP
  • Significance:
    • Interaction increases the power of verification
    • Strong connections to cryptography and blockchains

Zero-Knowledge Proofs​

  • Goal: prove possession of knowledge without revealing it.
  • Classic example: zero-knowledge proof for 3-COLOR.
  • Key properties:
    • Completeness
    • Soundness
    • Zero-knowledge

Widely used in cryptography and blockchain systems.

Randomness and Probabilistic Methods​

  • Randomized algorithms: use randomness to gain efficiency or simplicity.
  • Complexity classes: RP, BPP.
  • Fundamental question:
    • Is randomness necessary, or can we remove it (derandomization)?

Logic, Lower Bounds, and Proof Complexity​

  • Circuit lower bounds: proving limits of computational models.
  • Bounded arithmetic: logical characterization of complexity classes.
  • Reverse mathematics: minimal axioms needed for proofs.

Connects logic, complexity, and proof theory.

Connections to Modern Fields​

  • Cryptography: security proofs, assumptions, zero-knowledge.
  • Blockchain: consensus, security, incentive mechanisms.
  • Machine Learning Theory: generalization, sample complexity.
  • Quantum Computing: quantum algorithms and complexity classes.