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. 

• Рекомендации

  • Статья является заглушкой и нуждается в расширении. 
  • Читателей призывают помочь Википедии, расширив статью.