Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
type: Item
instance of: scholarly article
title: Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
zbMATH Open document ID: 1094.03044
author: Samuel R. Buss
published in: Theoretical Computer Science
publication date: 2006-08-16T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 5047250
zbMATH Keywords: propositional logic
zbMATH Keywords: resolution
zbMATH Keywords: proof complexity
zbMATH Keywords: graph connectivity
zbMATH Keywords: Hex game
MaRDI profile type: Publication
full work available at URL: j.tcs.2006.03.011
OpenAlex ID: W2086897006
cites work: The independence of the modulo \(p\) counting principles
cites work: The relative complexity of NP search problems
cites work: Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
cites work: An exponential separation between the parity principle and the pigeonhole principle
cites work: On Interpolation and Automatization for Frege Systems
cites work: Hex strategy: making the right connections
cites work: Polynomial size proofs of the propositional pigeonhole principle
cites work: Cutting planes, connectivity, and threshold logic
cites work: Linear gaps between degrees for the polynomial calculus modulo distinct primes
cites work: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
cites work: The relative efficiency of propositional proof systems
cites work: The Game of Hex and the Brouwer Fixed-Point Theorem
cites work: Lower bounds to the size of constant-depth propositional proofs
cites work: Q4856172
cites work: An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
cites work: Q4135772
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: Exponential lower bounds for the pigeonhole principle
DOI: 10.1016/J.TCS.2006.03.011
description: scientific article