544 Appendix A Search Procedures and Computational Complexity
of nondeterministic choices. Because each nondeterministic choice corresponds to
spawning a set of parallel CPUs, the set of execution traces can be represented as
an execution tree in which each node represents one of the iterations or recursive
invocations of the procedure, the children of each node represent the subprocesses
spawned by the procedure at this point of its iteration or recursion, and each path
in the tree represents an execution trace. This tree is called the procedure’s search
tree or search space.
Here are some of the properties that a problem-solving procedure may have.
•
Soundness. A deterministic procedure is sound if, whenever it is invoked on
some problem P and returns ...