Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HITTING FORMULAS:
Reports tagged with hitting formulas:
TR23-016 | 22nd February 2023
Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Proving Unsatisfiability with Hitting Formulas

Revisions: 1

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>




ISSN 1433-8092 | Imprint