Громов М.  

Сравнение сложности вычисления функций q-значной логики двумя классами ветвящихся программ

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

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


To reports list