Proofs with monotone cuts (Q2888631)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Proofs with monotone cuts |
scientific article; zbMATH DE number 6040456
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Proofs with monotone cuts |
scientific article; zbMATH DE number 6040456 |
Statements
Proofs with monotone cuts (English)
0 references
1 June 2012
0 references
proof complexity
0 references
monotone sequent calculus
0 references
Classical propositional proofs of arbitrary formulas with arbitrary cuts are quasipolynomially simulated by proofs with cuts only on monotone formulas. This is done using threshold formulas \(\theta^n_k(x_0,\dots,x_{n-1})\iff |\{i<n : x_i=1\}|\geq k\). Earlier this was done for proofs of monotone sequents.
0 references
