Правильная функция сложности
Надлежащая функция сложности — это функция f , отображающая натуральное число в натуральное число такая, что:
- f не убывает;
- существует с k -строками машина Тьюринга M на любом вводе длины n такая, что M останавливается после O( n + f ( n )) шагов, использует пространство O( f ( n )) и выводит f ( n ) последовательных пробелов .
Если f и g — две собственные функции сложности, то f + g , fg и 2 ж также являются собственными функциями сложности.
Подобные понятия включают честные функции, функции, конструируемые в пространстве и функции, конструируемые во времени .
Ссылки
[ редактировать ]Myashnikov, Alexei; Shpilrain, Vladimir; Ushakov, Vladimir (2008). Group-based Cryptography . Birkhauser. p. 28. ISBN 978-3-7643-8826-3 .