Automating tree-like resolution in time n^o( n) is \textsf{ETH}-hard

DOI10.1016/J.PROCS.2021.11.021MaRDI QIDQ6890908zbMATH OpenFDO

Authors Susanna F. de Rezende

Publication date 2 December 2025

Published in Procedia Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.PROCS.2021.11.021

zbMATH Keywords

automatabilityexponential time hypothesistree-like resolution

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited in

(1)

• Proving unsatisfiability with hitting formulas

This page was built for publication: Automating tree-like resolution in time \(n^{o(\log n)}\) is \textsf{ETH}-hard

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