Abstract
It was previously shown that a slight variant of the loop-programs produces a hierarchy of classes of functions defined by modified loop-programs, such that
is the set
of functions computable in a polynomial number of steps by such programs.
Here, an element of nondeterminism is introduced into loop-programs to produce a corresponding hierarchy . Designating the set of functions polynomially computable by nondeterministic programs by
we prove that
if
.We also prove that
.for n>2.
Finally, an element of non-determinism is introduced in the more general PL- programs, with parallel results.