Propositional Proof Complexity and Disjoint NP-Pairs I

We investigate strong propositional proof systems like Frege systems and their relations to disjoint NP-pairs. Proving lower bounds to the proof size of strong propositional proof systems (under suitable complexity theoretic assumptions) constitutes a major objective of the project. As an important tool we use the connection of propositional proof systems to disjoint NP-pairs and bounded arithmetic.
We investigate strong propositional proof systems like Frege systems and their relations to disjoint NP-pairs. Proving lower bounds to the proof size of strong propositional proof systems (under suitable complexity theoretic assumptions) constitutes a major objective of the project. As an important tool we use the connection of propositional proof systems to disjoint NP-pairs and bounded arithmetic.