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
A new proof of the weak pigeonhole principle, 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