Syllabus and references for the course The "P=NP?" problem
I do not list original references (with the exception of historic references in Lecture 2) but rather, whenever possible, selected survey articles or monographs that might serve best as starting points for an exploration of the respective areas. Many other references to monographs, lecture notes or surveys can be found at the web page of the Electronic Colloquium on Computational Complexity.
LECTURE 1: Examples, computational classes, the problem.
Examples: deciding the existence of a solution, finding an optimal one and counting the number of solutions in: satisfiability, Diophantine equations over finite fields (or bounded solutions over integers), travelling salesman problem.
Coding of inputs, O- and \Omega - notation. Decision problems as formal languages, reducing search problems to decision problems. Turing machine model, time measure, time classes P and EXP.
Definitions of NP: prover-verifier, non-determinism. The problem.
HW: Inclusions of P in NP in EXP, the equivalence of the two definitions of NP.
References:
- M.Sipser: Introduction to the theory of computation, PWS Publ.Comp.. 1997.
(This is an excellent reference for the next several lectures too.)
- S.Smale: Mathematical problems for the next century, Mathematical Intelligencer, 20(2), (1998), pp.7-15.
LECTURES 2 and 3: p-time reducibility,NP-completeness. History.
Definitions of p-time reducibility, NP-completeness. Cook's theorem.
Examples of NP-complete problems: SAT, 3-SAT, clique, 3-colorability, graph embedding, travelling salesman problem, Nullstellensatz over finite fields, bounded Hilbert's 10th problem, integer linear programming, subsetsum problem, hitting set and covering set problems.
Non-examples: 2-SAT, primeness, graph isomorphism, the existence of a bounded divisor.
History: theory of algorithms, Turing, Church, Kleene, Godel. Hilbert's 10th problem and the entschiedungsproblem (decide the truth in predicate calculus). Scholz's (1952) and Asser's (1955) spectrum problem. Godel's (1956) letter to J. von Neumann. Automated theorem proving.
1960s. Feasible = p-time and various notions close to NP: Bennet, Cobham, Edmonds, Rabin. Relevant results (recursion-theoretic in spirit): M.Blum, Hartmanis, Stearns.
1970s. Defining moment: Cook (1971), Karp (1972), Levin (1973).
References:
- M.R.Garey, and D.S.Johnson: Computers and intractability. (1979). New York, W.H.Freeman and Co..
- Sipser's book listed in Lecture 1
Historic references:
- G.Asser: Das Reprasentantenproblem im Pradikatenkalkul der ersten Stufe mit Identitat, Zietschr.f.Mathematisches Logik u. Grundlagen der Math. 1, (1955), pp.252-263.
- S.A.Cook: The complexity of theorem proving procedures, in: Proc. 3rd Annual ACM Symp. on Theory of Computing, (1971), pp. 151-158. ACM Press.
- K.Godel: a letter to J.von Neumann, in Sipser's article listed above, or in: "Arithmetic, Proof Theory and Computational Complexity", eds. P. Clote and J. Krajicek, Oxford Press, (1993).
- R.M.Karp: Reducibility Among Combinatorial Problems, Complexity of Computer Computations, pp. 85-103, Plenum Press, (1972).
- L.Levin: Universal Search Problems (in Russian), Problemy Peredachi Informatsii (= Problems of Information Transmission), 9(3), pp.265-266, (1973).
A partial English translation in: B.A.Trakhtenbrot: A Survey of Russian Approaches to Perebor (Brute-force Search) Algorithms. Annals of the History of Computing 6(4):384-400, 1984.
- H.Scholz: Problem #1: Ein ungelostes Problem in der symbolisches Logik, J.Symbolic Logic, 17, (1952), pp.160.
- M.Sipser: The history and status of the P versus NP question, in: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, (1992), pp.603-618. ACM Press
LECTURE 4: Structural complexity. Oracle results.
Hartmanis's theorem and its relativisation, oracle computations, the polynomial-time hierarchy.
Space bounded machines, Savitch's theorem, Immerman-Szelepscenyi theorem.
Limits to methods: Baker-Gill-Solovay theorem.
References:
- T.Baker, J.Gill, and R.Solovay: Relativizations of the P =? NP question, SIAM J. of Computing, Vol.4, (1975), pp.431-442.
- Sipser's book listed in Lecture 1
LECTURE 5: Combinatorial approach: boolean complexity.
Machines and circuits, Savage's theorem. Shannon's counting argument. Razborov's lower bound for monotone circuits.
Overview of known lower bounds. Remarks on topics not included (e.g. communication complexity).
References:
- R.Boppana, M.Sipser: Complexity of finite functions. in: Handbook of Theoretical Computer Science, ed.J. van Leeuwen, (1990), pp.758-804.
LECTURE 6: Cryptographic conjectures. The notion of natural (lower bound) proofs.
Pseudo-random number generators, one-way functions. Examples: factoring, discrete logarithm. The "standard cryptographic" conjecture (about the existence of hard pseudo-random number generators).
Natural (properties in lower bound) proofs. Limits to combinatorial proof methods: Razborov-Rudich's theorem on the non-existence of natural lower bound proofs for general circuits. Remark on formal complexity measures.
References:
- A.A.Razborov, S.Rudich: Natural proofs, in: Proc. 26th Annual ACM Symp. on the Theory of Computing, (1991), pp.201-213. ACM Press.
LECTURE 7: Relations to mathematical logic.
Direct relations: Hilbert's 10th problem and Matijasevic's theorem, and NP-completeness of bounded Nullstellensatz. The spectrum problem and finite model theory. The bounded arithmetic language, the hierarchy of its formulas and the polynomial time hierarchy.
Deeper ones: propositional proof systems, relations of bounded arithmetic to propositional proof systems ("model theory" of proof systems). The fundamental problem of about lengths-of-proofs for (extended) Frege systems.
References:
- J.Krajicek: Bounded arithmetic, propositional logic, and complexity theory, Encyclopedia of Mathematics and Its Applications, Vol. 60, Cambridge University Press, (1995).
- P.Pudlak: The lengths of proofs, in: Handbook of Proof Theory, ed. S.R.Buss, North-Holland, (1998).
- You may also see the bibliography from my course Lengths of propositional proofs.
LECTURE 8: The PCP-theorem. Approximations of NP-complete problems.
The Prover - Verifier definition of NP revisited, the definition of PCP classes. The PCP theorem.
Non-approximability results.
Example: the linearity test.References:
- A complete presentation of the proof of the PCP theorem, including relations to approximations of NP-problems:
S. Arora: Probabilistic Checking of Proofs and Hardness of Approximation Problems , Technical Report CS-TR-476-94, Princeton University, 1995. (Ph.D thesis.)
- The original paper (this is the journal version, the preprint appeared in 1992):
S.Arora, C.Lund, R.Motwani, M.Sudan, and M.Szegedy: Proof verification and the hardness of approximation problems.
- Lecture notes:
E.W. Mayr, H.J.Prmel, A.Steger (Eds.): Lectures on Proof Verification and Approximation Algorithms Lecture Notes in Computer Science, Vol.1367