PR (сложность)
PR — это класс сложности всех примитивно-рекурсивных функций или, что то же самое, набор всех формальных языков , которые могут быть решены за время, ограниченное такой функцией. Сюда входят сложение , умножение , возведение в степень , тетрация и т. д.
Функция Аккермана является примером функции, которая не является примитивно-рекурсивной, показывая, что PR строго содержится в R (Cooper 2004:88).
С другой стороны, мы можем «перенумеровать» любое рекурсивно перечислимое множество (см. также его класс сложности RE ) примитивно-рекурсивной функцией в следующем смысле: учитывая входные данные ( M , k ), где M — машина Тьюринга и k является целым числом, если M останавливается в течение k шагов, выведите M ; в противном случае ничего не выводить. Тогда объединение выходов по всем возможным входам ( M , k ) — это именно то множество M, которое остановилось.
Пиар строго содержит ЭЛЕМЕНТАРНО .
ПР не содержит «ПР-полных» задач (при условии, например, что сокращения относятся к ЭЛЕМЕНТАРНЫМ). На практике многие проблемы, которые не связаны с пиаром, а выходят за его рамки, -полный (Шмитц 2016).
Ссылки [ править ]
- С. Барри Купер (2004). Теория вычислимости . Чепмен и Холл. ISBN 1-58488-237-9 .
- Герберт Эндертон (2011). Теория вычислимости . Академическая пресса. ISBN 978-0-12-384-958-8 .
- Шмитц, Сильвен (2016). «Иерархии сложности, выходящие за рамки элементарного». Транзакции ACM по теории вычислений . 8 : 1–36. arXiv : 1312.5686 . дои : 10.1145/2858784 . S2CID 15155865 .
Внешние ссылки [ править ]
- Зоопарк сложности : PR .