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