Publication:4218929
From MaRDI portal
zbMath0910.03036MaRDI QIDQ4218929
Toniann Pitassi, Samuel R. Buss
Publication date: 15 November 1998
upper bounds; lower bounds; weak pigeonhole principle; monotone resolution rule; normal form for resolution proofs; tree-like resolution proofs
Related Items
Unnamed Item, An Introduction to Lower Bounds on Resolution Proof Systems, Resolution and the binary encoding of combinatorial principles, A new proof of the weak pigeonhole principle, Propositional proof complexity, Unit read-once refutations for systems of difference constraints, Parameterized proof complexity, Optimal length resolution refutations of difference constraint systems, Resolution over linear equations and multilinear proofs, Resolution lower bounds for the weak functional pigeonhole principle., Space bounds for resolution, Lower bounds for the weak pigeonhole principle and random formulas beyond resolution, Resolution lower bounds for perfect matching principles, Improved algorithms for optimal length resolution refutation in difference constraint systems, Width versus size in resolution proofs, Space Complexity in Polynomial Calculus