Можно ли смоделировать чередования в ?

9

Пусть ATISP(f(n),g(n)) будет классом языков, определяемым чередующимися машинами Тьюринга, которые останавливаются во времени f(n) используя пространство g(n) . Пусть AALTSP(f(n),g(n)) будет классом языков, определяемым чередующимися машинами Тьюринга, которые останавливаются, используя чередования f(n) и пробел g(n) .

Руццо доказал, что . Он также показал, что .NCk=ATISP(logkn,logn)NCkAALTSP(logkn,logn)NCk+1

Является ли ?NCk=AALTSP(logkn,logn)

argentpepper
источник

Ответы:

11

Конечно, равенства и включения, заявленные в вопросе, справедливы только для равномерного . Класс совпадает с классом , поэтому вопрос такой же, как .NСКAALTSп(журналКN,журналN)AСКNСКзнак равноAСК

В частности, случай подразумевает, что равен и даже , поскольку . Кзнак равно1LNLLогСFLNC1LNLLogCFLAC1

Ян Йоханнсен
источник