# Automating Resolution is NP-Hard

arXiv: https://arxiv.org/abs/1904.02991 · HTML: https://mlsanity.com/paper/1904.02991/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2019.

## Built on by (most cited first, 2 of 2)

- [Intersymbolic AI: Interlinking Symbolic AI and Subsymbolic AI](https://mlsanity.com/paper/2406.11563/) (2024)
- [Learning algorithms versus automatability of Frege systems](https://mlsanity.com/paper/2111.10626/) (2021)

## Abstract (arXiv)

We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatizable unless P = NP. Indeed, we show it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatizable in subexponential time or quasi-polynomial time unless NP is included in SUBEXP or QP, respectively.