Proof Set Search

Proof-set search (PSS) is a best-first search method for and/or graphs which is closely related to Allis' proof-number search. PSS addresses a problem that has plagued search algorithms on and/or graphs for a long time: overestimating the solution cost of those subgraphs that can be reached through many different paths. PSS computes proof and disproof sets instead of proof numbers, which are upper bounds of the size of such sets. This method eliminates the problem of counting the same node more than once. The sets computed by proof-set search provide a provably better approximation to the hard-to-compute minimal proof sets than is possible with proof numbers.


M. Müller. Proof-set search. In J. Schaeffer, M. Müller, and Y. Björnsson, editors, Computers and Games 2002, number 2883 in Lecture Notes in Computer Science, pages 88-107. Springer Verlag, 2003.
Created: Sep 26, 2000 Last modified: Jun 19, 2009

Martin Müller