Доказательства принадлежности рефал-5 функций некоторым подклассам FP-SPACE
PROOFS OF REFAL-5 FUNCTION BELONGING TO SOME SUBCLASSES OF FP-SPACE
PROOFS OF REFAL-5 FUNCTION BELONGING TO SOME SUBCLASSES OF FP-SPACE
Открыто 
Вводятся иерархии классов сложности функций как из FP, так и из FP-SPACE. В статье доказывается теорема о замкнутости классов функций этих иерархий, а также классов функций FP||LIN-SPACE и FP||QLIN-SPACE и классов предикатов P||LIN-SPACE и P||QLIN-SPACE относительно определения рефал-5 функций с ограниченными сверху числом рекурсивных вызовов и величиной использованной памяти. С. 3-8.
Complexity classes hierarchies for functions from both FP and FP-SPACE classes are introduced. Theorems about closure of these function classes of hierarchies as well as the classes of functions FP||LIN-SPACE and FP||QLIN-SPACE and classes of predicates P||LIN-SPACE and P||QLIN-SPACE under the definition of Refal-5 functions with bounded numbers of recursive calls and the used memory size are proved.
Complexity classes hierarchies for functions from both FP and FP-SPACE classes are introduced. Theorems about closure of these function classes of hierarchies as well as the classes of functions FP||LIN-SPACE and FP||QLIN-SPACE and classes of predicates P||LIN-SPACE and P||QLIN-SPACE under the definition of Refal-5 functions with bounded numbers of recursive calls and the used memory size are proved.
Ключевые слова: машина Тьюринга, полиномиальное число шагов, рефал-5, подклассы класса FP-SPACE, подклассы класса FP.
Keywords: Turing machine, polynomial number of steps, Refal-5, subclasses of the class FP-SPACE, subclasses of the class FP.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть