On the amount of nondeterminism and the power of nondeterminism and the power of verifying. - Cai, Liming (SIAM journal on computing.)
The relationship between nondeterminsm and other computational resources is investigated based on the "guess-then-check" model GC. Systematic techniques are developed to construct natural complete languages for the classes defined by this model. This improves a number of previous results in the study of limited nondeterminism. Connections of the model GC to computational optimization problems are exhibited.