Proof systems that take advice
type: Item
instance of: scholarly article
title: Proof systems that take advice
zbMATH Open document ID: 1222.03062
author: Olaf Beyersdorff
author: Johannes Köbler
author: Sebastian Müller
published in: Information and Computation
publication date: 2011-07-27T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5932316
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: computational complexity
zbMATH Keywords: proof systems
zbMATH Keywords: advice
zbMATH Keywords: instance complexity
zbMATH Keywords: polynomially bounded proof systems
zbMATH Keywords: optimal proof systems
MaRDI profile type: Publication
full work available at URL: j.ic.2010.11.006
OpenAlex ID: W2059785423
Wikidata QID: Q59902997
cites work: Q4501542
cites work: Logarithmic advice classes
cites work: Q4039803
cites work: Nondeterministic Instance Complexity and Proof Systems with Advice
cites work: A tight Karp-Lipton collapse result in bounded arithmetic
cites work: Does Advice Help to Prove Propositional Tautologies?
cites work: Tally languages and complexity classes
cites work: Q4418680
cites work: Resource-bounded Kolmogorov complexity revisited
cites work: Competing provers yield improved Karp-Lipton collapse results
cites work: Consequences of the provability of NP ⊆ P/poly
cites work: The relative efficiency of propositional proof systems
cites work: Optimal proof systems imply complete sets for promise classes
cites work: Propositional proof systems, the consistency of first order theories and the complexity of computations
cites work: Instance complexity
cites work: Q4215637
DBLP publication ID: journals/iandc/BeyersdorffKM11
DOI: 10.1016/J.IC.2010.11.006
description: scientific article; zbMATH DE number 5932316