One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow (JSL 79), where they defined propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Krajicek (JSL 07) have ... more >>>

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice. In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages? Depending on the complexity of the underlying ... more >>>