Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-075 | 7th July 2008 00:00

Nondeterministic Instance Complexity and Proof Systems with Advice

RSS-Feed




TR08-075
Authors: Olaf Beyersdorff, Johannes Köbler, Sebastian Müller
Publication: 28th August 2008 19:52
Downloads: 1616
Keywords: 


Abstract:

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 language and the amount and type of the advice used by the proof system, we obtain different characterizations for this problem. In particular, we show that for a language L, the above question is tightly linked with the question whether L has small nondeterministic instance complexity.



ISSN 1433-8092 | Imprint