Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SEBASTIAN MÜLLER:
All reports by Author Sebastian Müller:

TR09-092 | 8th October 2009
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

Proof Systems that Take Advice

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 >>>


TR08-075 | 7th July 2008
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

Nondeterministic Instance Complexity and Proof Systems with Advice

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 ... more >>>




ISSN 1433-8092 | Imprint