On Computation Complexity of True Proof Number Search

02/08/2021
by   Chao Gao, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset