Monotone simulations of non-monotone proofs.
type: Item
instance of: scholarly article
title: Monotone simulations of non-monotone proofs.
zbMATH Open document ID: 1034.03054
DOI: 10.1016/S0022-0000(02)00020-X
author: Albert Atserias
author: Nicola Galesi
author: Pavel Pudlák
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 1910853
zbMATH Keywords: complexity of proofs
MaRDI profile type: Publication
cites work: Sorting in \(c \log n\) parallel steps
cites work: Monotone proofs of the pigeon hole principle
cites work: Q4828877
cites work: Polynomial size proofs of the propositional pigeonhole principle
cites work: On the computational content of intuitionistic propositional proofs
cites work: The relative efficiency of propositional proof systems
cites work: The intractability of resolution
cites work: Q4856172
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Q4934563
cites work: Q3758729
cites work: Proof theory. 2nd ed
cites work: The gap between monotone and non-monotone circuit complexity is exponential
cites work: Short monotone formulae for the majority function
cites work: Q3762226
full work available at URL: s0022-0000(02)00020-x
OpenAlex ID: W2158912767
Recommended article: Proof-complexity results for nonmonotonic reasoning
Recommended article: Logic of Non-monotonic Interactive Proofs
Recommended article: Proof complexity of monotone branching programs
Recommended article: Q5445419
Recommended article: From positive and intuitionistic bounded arithmetic to monotone proof complexity
Recommended article: Proofs from simulations and modular annotations
Recommended article: Q4825686
Recommended article: Simulating strong practical proof systems with extended resolution
Recommended article: The deduction rule and linear and near-linear proof simulations
Recommended article: Q4708605
description: scientific article; zbMATH DE number 1910853