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.


Principal Investigators
Köbler, Johannes Prof. Dr. (Details) (Algorithms and Complexity II)

Duration of Project
Start date: 04/2006
End date: 03/2008

Last updated on 2020-09-03 at 23:13