СК (сложность)
В сложности вычислений теории SC (Класс Стива, названный в честь Стивена Кука ) [1] — это класс сложности задач, решаемых детерминированной машиной Тьюринга за полиномиальное время (класс P ) и полилогарифмическое пространство (класс PolyL ) (т. е. O ((log n ) к ) пространство для некоторой константы k ). Его также можно назвать DTISP(poly,polylog) , где DTISP означает детерминированное время и пространство . Обратите внимание, что определение SC отличается от определения P ∩ PolyL , поскольку для первого требуется, чтобы один алгоритм работал как в полиномиальном времени, так и в полилогарифмическом пространстве; в то время как для последнего будет достаточно двух отдельных алгоритмов: один, который работает за полиномиальное время, и другой, который работает в полилогарифмическом пространстве. (Неизвестно, ли SC и P ∩ PolyL эквивалентны ).
DCFL , строгое подмножество контекстно-свободных языков, распознаваемых детерминированными автоматами с выталкиванием вниз , содержится в SC , как показал Кук в 1979 году. [2] Вопрос открыт, можно ли распознать все контекстно-свободные языки в SC , хотя известно, что они находятся в P ∩ PolyL . [3]
Он открыт, если направленная st-связность есть в SC , хотя известно, что она находится в P ∩ PolyL (благодаря алгоритму DFS и теореме Савича ). Этот вопрос эквивалентен вопросу NL ⊆ SC .
RL и BPL — это классы задач, приемлемые вероятностными машинами Тьюринга в логарифмическом пространстве и полиномиальном времени. Ноам Нисан показал в 1992 году слабый результат дерандомизации , заключающийся в том, что оба они содержатся в SC . [4] Другими словами, при наличии полилогарифмического пространства детерминированная машина может моделировать в логарифмическом вероятностные алгоритмы пространстве.
Ссылки [ править ]
- ^ Зоопарк сложности : SC
- ^ С.А. Кук. Детерминированные КЛЛ принимаются одновременно в полиномиальном времени и логарифмическом пространстве. Материалы ACM STOC'79, стр. 338–345. 1979.
- ^ TCS Stack Exchange: анализ CFG с использованием пространства o (n ^ 2)
- ^ Нисан, Ноам (1992), «RL ⊆ SC», Труды 24-го симпозиума ACM по теории вычислений (STOC '92) , Виктория, Британская Колумбия, Канада, стр. 619–623, doi : 10.1145/129712.129772 , S2CID 11651375
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .