scientific article; zbMATH DE number 1114023

MaRDI QIDQ4375792zbMATH OpenFDO

Authors Stasys Jukna

Publication date 8 February 1998

zbMATH Keywords

projective planesexponential lower boundaffine planespigeonhole principleblocking principleshitting set principlesemantic resolution proof

Mathematics Subject Classification ID

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

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

(4)

• Resolution lower bounds for the weak functional pigeonhole principle.
• Resolution lower bounds for perfect matching principles
• Computing generating sets of minimal size in finite algebras
• On the complexity of semantic self-minimization

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)