SC (сложность)
-
Определение класса SC
- SC — это класс задач, решаемых детерминированной машиной Тьюринга за полиномиальное время и полилогарифмическое пространство.
- SC также известен как DTISP (poly, polylog).
-
Отличие от класса P ∈ PolyL
- Определение SC требует одновременного выполнения алгоритма за полиномиальное время и в полилогарифмическом пространстве.
- Для класса P ∈ PolyL достаточно двух отдельных алгоритмов.
-
Примеры задач в классе SC
- DCFL, строгое подмножество контекстно-свободных языков, содержится в SC.
- Вопрос о том, все ли контекстно-свободные языки распознаваемы в SC, остается открытым.
- Направленная st-связность также находится в SC, но известно, что она принадлежит классу P ∈ PolyL.
-
Эквивалентность с другими классами
- Вопрос о том, NL ∈ SC, остается открытым.
- RL и BPL — это классы задач, приемлемые для вероятностных машин Тьюринга, которые также содержатся в SC.
-
Рекомендации
- Статья является заглушкой и нуждается в расширении.
- Читателей призывают помочь Википедии, расширив статью.
Полный текст статьи: