Disjoint DNF tautologies with conflict bound two

MaRDI QIDQ3515550zbMATH OpenFDO

Authors Balázs Szörényi

Publication date 29 July 2008

zbMATH Keywords

decision treesread-once resolution refutationunsatisfiable hitting clause sets

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• How Many Conflicts Does It Need to Be Unsatisfiable?
• DNF tautologies with a limited number of occurrences of every variable
• Variable and term removal from Boolean formulae
• Unsatisfiable CNF formulas contain many conflicts
• scientific article; zbMATH DE number 3952007

Cited in

(2)

• The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant
• Are hitting formulas hard for resolution?

This page was built for publication: Disjoint DNF tautologies with conflict bound two

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