scientific article; zbMATH DE number 1114023

zbMATH Open0890.03032MaRDI QIDQ4375792FDOQ4375792

Stasys Jukna

Publication date: 8 February 1998

Title of this publication is not available (Why is that?)

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

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)

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)