Restricted cutting plane proofs in Horn constraint systems

DOI10.1007/978-3-030-29007-8_9MaRDI QIDQ2180223zbMATH OpenOpenAlexFDO

Authors Hans Kleine Büning, R. Chandrasekaran, Piotr Wojciechowski, K. Subramani

Publication date 13 May 2020

Full work available at URL https://doi.org/10.1007/978-3-030-29007-8_9

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) Integer programming (90C10) Logic in computer science (03B70) Structure of proofs (03F07)

Recommendations

• On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
• On the complexity of cutting-plane proofs
• Input Proofs and Rank One Cutting Planes
• scientific article; zbMATH DE number 408793
• scientific article; zbMATH DE number 512977

Cited in

(9)

• On the copy complexity of width 3 Horn constraint systems
• Unit read-once refutations for systems of difference constraints
• On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
• On a generalization of Horn constraint systems
• Analyzing read-once cutting plane proofs in Horn systems
• Farkas Bounds on Horn Constraint Systems
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• Exact and parameterized algorithms for read-once refutations in Horn constraint systems
• On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations

This page was built for publication: Restricted cutting plane proofs in Horn constraint systems

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