R (сложность) - R (complexity) - Wikipedia
В теория сложности вычислений, р это класс проблемы решения решаемый Машина Тьюринга, который представляет собой набор всех рекурсивные языки.
Эквивалентные составы
R равно множеству всех итоговых вычислимые функции.
Отношения с другими классами
Поскольку мы можем решить любую проблему, для которой существует распознающий а также со-распознаватель, просто чередуя их, пока не будет получен результат, класс равен RE ∩ co-RE.
Рекомендации
- Блюм, Ленор, Майк Шуб и Стив Смейл. «К теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины». Бюллетень (новая серия) Американского математического общества 21.1 (1989): 1-46.
внешняя ссылка
| P ≟ NP | Этот теоретическая информатика –Связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |