Proof complexity of monotone branching programs
type: Item
instance of: scholarly article
title: Proof complexity of monotone branching programs
DOI: 10.1007/978-3-031-08740-0_7
author: Anupam Das
author: Avgerinos Delkos
publication date: 2022-12-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/2102.06673
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7627919
zbMATH Keywords: proof complexity
zbMATH Keywords: branching programs
zbMATH Keywords: monotone complexity
MaRDI profile type: Publication
OpenAlex ID: W4285178183
cites work: Monotone versus positive
cites work: Q2754140
cites work: Monotone simulations of non-monotone proofs.
cites work: Q5874198
cites work: Expander Construction in VNC1
cites work: Towards NP-P via proof complexity and search
cites work: The relative efficiency of propositional proof systems
cites work: A recursion-theoretic characterisation of the positive polynomial-time functions
cites work: Q4036700
cites work: A sorting network in bounded arithmetic
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Positive versions of polynomial time
cites work: Q5593647
cites work: Q4474836
cites work: Q3758729
cites work: Lower bounds on monotone complexity of the logical permanent
Recommended article: Q5092485
Recommended article: Q5874198
Recommended article: Q3690219
Recommended article: On the proof complexity of logics of bounded branching
Recommended article: Q4318222
Recommended article: Q3335688
Recommended article: Positive and Negative Proofs for Circuits and Branching Programs
Recommended article: Positive and negative proofs for circuits and branching programs
Recommended article: Q4842542
Recommended article: From positive and intuitionistic bounded arithmetic to monotone proof complexity
description: scientific article; zbMATH DE number 7627919