On Computation Complexity of True Proof Number Search
Not on the map. Why?
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.
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.
Builds on
0 of 38 references.
No references here yet.
Built on by
Not cited yet.