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:



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:



Historic references:



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:



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:



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:



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:



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: