# On Computation Complexity of True Proof Number Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 38 references that are in the map.
- First posted on arXiv 8 Feb 2021.

## Abstract (arXiv)

We point out that the computation of true proof and disproof numbers for proof number search in arbitrary directed acyclic graphs is NP-hard, an important theoretical result for proof number search. The proof requires a reduction from SAT, which demonstrates that finding true proof/disproof number for arbitrary DAG is at least as hard as deciding if arbitrary SAT instance is satisfiable, thus NP-hard.