Polynomial computations in non-deterministic loop-programs and PL-programs

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.

Keywords:

• Loop programs
• PL programs
• Polynomially computable functions
• Non-deterministic programs

C.R. Categories:

• 5.24
• 5.25