- Класс R
-
Эта статья слишком короткая. Пожалуйста, дополните её ещё хотя бы несколькими предложениями и уберите это сообщение. Если статья останется недописанной, она может быть выставлена к удалению. Для указания на продолжающуюся работу над статьёй используйте шаблон {{subst:L}}.
Администраторам: эта пометка оставлена Ink 08:26, 15 октября 2011 (UTC). Просьба очень короткие заготовки статей ранее чем через два дня после создания не удалять.В теории сложности вычислений классом R (от англ. the recursive languages) называют множество всех рекурсивных языков. Эквивалентно класс R можно определить как множество задач распознавания (англ.) разрешимых на машине Тьюринга. Класс R равен пересечению классов RE и co-RE.
Для улучшения этой статьи желательно?: - Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Cчитаются лёгкими P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP Предпологаются сложными NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM Cчитаются сложными EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH Список алгоритмов Категория:- Классы сложности
Wikimedia Foundation. 2010.