Syllabus for P. Pudlak's lectures
at the
Fall school(Sept.'02)
Proof systems and integer linear programming
Heuristics for NP-complete problems can be interpreted as
propositional proof systems. In integer linear programming a well
known cutting plane procedure has been extensively studied and
examples have been found that require exponentially many
steps. For other systems only partial results are known, in
particular, several systems possess the feasible interpolation property.
In this lecture we shall introduce some basic concepts and results in
linear programming. Then we shall give a survey of proof systems that has
been studied and prove some theorems about them.
References:
L. Lovasz: On the Shannon capacity of graphs, IEEE Transactions on
Information Theory 25, 1979
L.Lovasz: Semidefinite programs and combinatorial optimization.
L Lovasz and A. Schrijver: Cones of matrices and set-functions and 0-1
optimization, SIAM J. on Optimization 1, 1991
P. Pudlak:
Lower bounds for resolution and cutting plane proofs and
monotone computations, JSL 62, 1997.
P. Pudlak:
On the complexity of propositional calculus, Logic Colloquium
1997, Cambridge 1999.
S. Dash:
On the matrix cuts of Lovasz and Schrijver and their use in
integer programming, PhD thesis,
TR 01-08.
