Proof complexity of monotone branching programs

DOI10.1007/978-3-031-08740-0_7OpenAlexW4285178183MaRDI QIDQ2104254

Anupam Das, Avgerinos Delkos

Publication date: 7 December 2022

Full work available at URL: https://arxiv.org/abs/2102.06673

zbMATH Keywords

branching programsproof complexitymonotone complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Proof complexity of monotone branching programs

Cites Work

• Towards NP-P via proof complexity and search
• A sorting network in bounded arithmetic
• Lower bounds on monotone complexity of the logical permanent
• Positive versions of polynomial time
• Monotone simulations of non-monotone proofs.
• Proof complexity of monotone branching programs
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone versus positive
• The relative efficiency of propositional proof systems
• Expander Construction in VNC1
• A recursion-theoretic characterisation of the positive polynomial-time functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Proof complexity of monotone branching programs