The "P=NP?" problem
Jan Krajicek, (Hilary term, Spring 1999, Oxford)
The "P = NP?" problem asks if any set of finite objects of a certain type (numbers, graphs, formulas, polynomials, ... ) encoded in a finite language that is accepted by a non-deterministic Turing machine in polynomial time is also decidable in polynomial time by a deterministic machine. More concretely but equivalently (by a theorem): can it be recognised algorithmically in polynomial time that a propositional formula is satisfiable, or that a graph can be 3-coloured, or that a system of polynomial equations over a finite field is solvable in the field, or that a Diophantine equation has a solution of absolute value bounded by a parameter, or ...?
It is generally conjectured that the answer is negative, but a proof of the conjecture seems to be far away.
The "P = NP?" problem is one of the most important open problems of contemporary mathematics (occasionally it is courageously listed in one breath with Riemann hypothesis and Poincaré conjecture). It also has many connections with other problems in computational complexity and mathematical logic.
The prerequisite for the course is just an elementary knowledge of the notion of a Turing machine. The aim of the course is to survey some of the best results related to the problem and to point out some of the connections, giving along the way examples of proofs and of open problems. In particular, we plan to discuss:
A (more detailed) syllabus and references are available separately.
- Basic definitions. History of the problem.
- NP-completeness.
- Related computational complexity classes and hierarchies. Oracle results: limitations on potential techniques of a solution.
- Combinatorial approach: boolean complexity.
- Cryptographic conjectures (on pseudo-random number generators and one-way functions). The notion of "natural (lower bound) proofs": another limitation on potential solution techniques.
- The PCP-theorem. Approximations of NP-complete problems.
- Relations to mathematical logic.
- Auxiliary (if time permits): computations over reals, extended Turing machine models, etc.