Name
Abstract | ||
|---|---|---|
Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajíček [1] have recently introduced the
notion of propositional proof systems with advice. In this paper we investigate the following question: Given a language L
, do there exist polynomially bounded proof systems with advice for L
? Depending on the complexity of the underlying language L 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 the above question is tightly linked with the question whether L has small nondeterministic instance complexity.
|
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-642-00982-2_14 | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
small nondeterministic instance complexity,proof systems,bounded arithmetic,nondeterministic instance complexity,language l,strong karp-lipton collapse result,polynomially bounded proof system,propositional proof system,different characterization,following question,underlying language,proof system | Discrete mathematics,Bounded arithmetic,Nondeterministic algorithm,Computer science,Proof complexity,Bounded function | Journal |
Volume | Issue | ISSN |
5457 | 075 | 0302-9743 |
Citations | PageRank | References |
5 | 0.48 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olaf Beyersdorff | 1 | 223 | 30.33 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Sebastian Müller | 3 | 7 | 1.20 |