Non-classical Aspects in Proof Complexity

Proof complexity focuses on the complexity of theorem proving procedures, a

topic which is tightly linked to questions from computational complexity (the

separation of complexity classes), first-order arithmetic theories (bounded arithmetic),

and practical questions as automated theorem proving. One fascinating

question in proof complexity is whether powerful computational resources as randomness

or oracle access can shorten proofs or speed up proof search. In this

dissertation we investigated these questions for proof systems that use a limited

amount of non-uniform information (advice). This model is very interesting as¿-

in contrast to the classical setting¿-it admits an optimal proof system as recently

shown by Cook and Krajícek. We give a complete complexity-theoretic classification

of all languages admitting polynomially bounded proof systems with advice

and explore whether the advice can be simplified or even eliminated while still

preserving the power of the system.

Propositional proof systems enjoy a close connection to bounded arithmetic.

Cook and Krajícek (JSL¿07) use the correspondence between proof systems with

advice and arithmetic theories to obtain a very strong Karp-Lipton collapse result

in bounded arithmetic: if SAT has polynomial-size Boolean circuits, then the

polynomial hierarchy collapses to the Boolean hierarchy. Here we show that this

collapse consequence is in fact optimal with respect to the theory PV, thereby

answering a question of Cook and Krajícek.

The second main topic of this dissertation is parameterized proof complexity, a

paradigm developed by Dantchev, Martin, and Szeider (FOCS¿07) which transfers

the highly successful approach of parameterized complexity to the study of proof

lengths. In this thesis we introduce a powerful two player game to model and

study the complexity of proofs in a tree-like Resolution system in a setting arising

from parameterized complexity. This game is also applicable to show strong

lower bounds in other tree-like proof systems. Moreover, we obtain the first lower

bound to the general dag-like Parameterized Resolution system for the pigeonhole

principle and study a variant of the DPLL algorithm in the parameterized setting.