scientific article; zbMATH DE number 1114023

MaRDI QIDQ4375792zbMATH OpenFDO

Authors Stasys Jukna

Publication date 8 February 1998

zbMATH Keywords

affine planesblocking principlesexponential lower boundhitting set principlepigeonhole principleprojective planessemantic resolution proof

Mathematics Subject Classification ID

Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Finite affine and projective planes (geometric aspects) (51E15) Blocking sets, ovals, (k)-arcs (51E21) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorics in computer science (68R05)

Recommendations

• Lower bounds for resolution and cutting plane proofs and monotone computations
• Exponential lower bounds for the pigeonhole principle
• Resolution lower bounds for the weak functional pigeonhole principle.
• scientific article; zbMATH DE number 1754651
• Resolution lower bounds for the weak pigeonhole principle

Cited in

(5)

• Resolution lower bounds for the weak functional pigeonhole principle.
• Resolution lower bounds for perfect matching principles
• On the complexity of semantic self-minimization
• Computing generating sets of minimal size in finite algebras
• Extending merge resolution to a family of QBF-proof systems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375792)