Класс 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 |
| Список алгоритмов | |
