SC (сложность)

В теории вычислительной сложности, SC(Класс Стива, названный в честь Стивена Кука ) - это класс сложности задач, решаемых с помощью детерминированной машины Тьюринга за полиномиальное время (класс P ) и полилогарифмическое пространство (класс PolyL ) (то есть O ((log n)) пространство для некоторой константы k). Его также можно назвать DTISP (poly, polylog), где DTISP обозначает детерминированное время и пространство. Обратите внимание, что определение SC отличается от P∩ PolyL, поскольку для первого требуется, чтобы один алгоритм выполнялся как в полиномиальном времени, так и в полилогарифмическом пространстве; в то время как для последнего будет достаточно двух отдельных алгоритмов: один работает за полиномиальное время, а другой - в полилогарифмическом пространстве. (Неизвестно, эквивалентны ли SC и P∩ PolyL ).

DCFL, строгое подмножество контекстно-свободных языков, распознаваемых детерминированными выталкивающими автоматами, содержится в SC, как показано Куком в 1979 году.

Он открыт, если направлено st-соединение в SC, хотя известно, что оно находится в P∩ PolyL ( из-за алгоритма DFS и теоремы Сэвича ). Этот вопрос эквивалентен NL ⊆ SC.

RL, а BPL - классы задач, приемлемые для вероятностных машин Тьюринга в логарифмическом пространстве и полиномиальном времени. Ноам Нисан показал в 1992 году слабый результат дерандомизации, поскольку оба они содержатся в SC . Другими словами, с учетом полилогарифмического пространства детерминированная машина может моделировать вероятностные алгоритмы логарифмического пространства.