Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIMULATIONS:
Reports tagged with simulations:
TR10-147 | 22nd September 2010
Dieter van Melkebeek, Thomas Watson

#### Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

TR12-018 | 24th February 2012
Joerg Flum, Moritz Müller

#### Some definitorial suggestions for parameterized proof complexity

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>

TR14-014 | 28th January 2014
Olaf Beyersdorff, Leroy Chew

#### The Complexity of Theorem Proving in Circumscription and Minimal Entailment

Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>>

TR14-032 | 8th March 2014
Olaf Beyersdorff, Leroy Chew

#### Tableau vs. Sequent Calculi for Minimal Entailment

In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (J. Autom. Reasoning, 1992). Our main result shows that OTAB-proofs can be efficiently translated into MLK-proofs, i.e., MLK p-simulates OTAB. The simulation is technically very involved ... more >>>

TR15-152 | 16th September 2015
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

#### Are Short Proofs Narrow? QBF Resolution is not Simple.

The groundbreaking paper `Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>>

TR16-011 | 27th January 2016
Olaf Beyersdorff, Ján Pich

#### Understanding Gentzen and Frege systems for QBF

Recently Beyersdorff, Bonacina, and Chew (ITCS'16) introduced a natural class of Frege systems for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted versions of these systems. Here we provide a comprehensive analysis of the new extended Frege system from Beyersdorff et al., denoted EF+\$\forall\$red, which is a ... more >>>

ISSN 1433-8092 | Imprint