Рассматривается вычисление q-значными ветвящимися упорядоченными 1- и 2-программами функций q-значной логики. В работе получены полиномиальная верхняя оценка сложности упорядоченных ветвящихся 2-программ и сверхполиномиальная нижняя оценка сложности упорядоченных ветвящихся 1-программ для одной и той же последовательности функций q-значной логики (q > 2). Тем самым показано существенное отличие этих двух классов ветвящихся программ.
| Файл тезисов: | 3ffThes.pdf |