Аннотация:
В статье показано, что при Тьюринговой кодировке натуральных чисел их простота проверяется однородными структурами за время, асимптотически совпадающее с половиной длины кода.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 02–01–00162.
Полный текст:
PDF файл (1395 kB)