The computing of q-valued functions with ordered branching 1- and 2-programs is considered.
The polynomial upper bound of the complexity of ordered branching 2-programs and superpolynomial lower bound of the complexity of ordered branching 1-programs computing one sequence of q-valued functions are obtained. Thereby the significant difference in computational power of these two classes of branching programs has been revealed.
| Abstracts file: | 3ffThes.pdf |