本科高年级Computation计划中
Computational complexity
Time and space complexity classes, P and NP, polynomial-time reductions, NP-completeness and the Cook–Levin theorem, and the status of the P versus NP problem.
math.comp.complexity-theory
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
25 项必需的前置知识（一直追溯到底）
你将学会
- Define P and NP and place standard problems in them.
- Prove NP-completeness of problems such as 3-SAT, vertex cover or graph 3-colouring by reductions.
- Explain what is known and unknown about P versus NP, and why cryptography relies on unproved hardness assumptions.
定义
- P is the class of decision problems solvable in polynomial time by a deterministic Turing machine.
- NP is the class of decision problems whose yes-instances have certificates that can be verified in polynomial time.
- A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time.
定理
- Cook–Levin: Boolean satisfiability (SAT) is NP-complete.
- P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, and P ≠ EXPTIME by the time hierarchy theorem.
- Whether P = NP is open; it is one of the Clay Mathematics Institute's Millennium Prize Problems.
常见误解
- Thinking NP stands for 'not polynomial'; it stands for nondeterministic polynomial time.
- Believing NP-complete problems cannot be solved in practice; many large instances are solved routinely.
可选发现
- Proof theory Proof complexity asks how long proofs of propositional tautologies must be; NP ≠ coNP holds if and only if no propositional proof system has polynomial-size proofs of all tautologies (Cook–Reckhow).
- ← Propositional logic and truth tables
- ← Algorithms, correctness and efficiency
- ← Cryptography
- ← Graph theory
- ← The probabilistic method
学习路径
延伸阅读
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (2009)
- Michael Sipser, Introduction to the Theory of Computation (1996)