NC = P последствия?

35

Сложность Zoo указывает в записи на EXP, что если L = P, то PSPACE = EXP. Поскольку NPSPACE = PSPACE от Savitch, насколько я могу судить, нижележащий аргумент отступа расширяется, чтобы показать, что Мы также знаем, что L NL NC P через ограниченную по ресурсам чередующуюся иерархию.

(NL=P)(PSPACE=EXP).

Если NC = P, следует ли это, что PSPACE = EXP?

Другая интерпретация вопроса в духе Ричарда Липтона: более вероятно, что некоторые задачи в P не могут быть распараллелены, чем то, что никакая процедура по экспоненциальному времени не требует большего, чем полиномиальное пространство?

Меня также интересовали бы другие «удивительные» последствия NC = P (чем меньше вероятность, тем лучше).

Редактировать: ответ Райана приводит к дальнейшему вопросу: какая самая слабая гипотеза, которая, как известно, гарантирует PSPACE = EXP?

  • В. Савич. Взаимосвязь между недетерминированными и детерминированными сложностями ленты, Журнал компьютерных и системных наук 4 (2): 177-192, 1970.
  • WL Ruzzo. О сложности единой схемы, Журнал компьютерных и системных наук 22 (3): 365-383, 1971.

Edit (2014): обновлена ​​старая ссылка Zoo и добавлены ссылки для всех других классов.

Андраш Саламон
источник
1
Я уверен, что я не единственный, кто не знает, что такое NC, вот ссылка: en.wikipedia.org/wiki/NC_%28complexity%29
Эмиль
@Andras: Еще одно следствие, которое, возможно, вы уже знаете, но еще не было упомянуто, заключается в том, что иерархия рухнет, поскольку имеет полные проблемы при -reductions , NCPL
Джошуа

Ответы:

28

Да. можно рассматривать как класс языков, распознаваемых чередующимися машинами Тьюринга, которые используют пространство и время. (Это было впервые доказано Руццо.) - это класс, в котором чередующиеся машины Тьюринга используют пространство но могут занимать до времени. Для краткости назовем эти классы и .NCO(logn)(logn)O(1)PO(logn)nO(1)ATISP[(logn)O(1),logn]=NCASPACE[O(logn)]=P

Предположим, что два класса равны. Заменив на в приведенном выше (т.е. применяя стандартные леммы перевода), получимn2n

TIME[2O(n)]=ASPACE[O(n)]=ATISP[nO(1),n]ATIME[nO(1)]=PSPACE .

Если тогда , так как в есть языки, полные .TIME[2O(n)]PSPACEEXP=PSPACEEXPTIME[2O(n)]

Изменить: Хотя приведенный выше ответ, возможно, более образовательный, вот более простой аргумент: уже следует из " содержится в пространстве полилога" и стандартного перевода. Примечание « содержится в Полилог пространстве» является намного слабее , чем гипотеза .EXP=PSPACEPPNC=P

Более подробно: Поскольку семейства цепей имеют глубину для некоторой константы, каждое такое семейство цепей может быть оценено в пространстве . Следовательно, . Таким образом, подразумевает . Применение перевода (замена на ) подразумевает . Существование полного языка в завершает аргумент.NC(logn)cO((logn)c)NCc>0SPACE[(logn)c]P=NCPc>0SPACE[(logn)c]n2nTIME[2O(n)]PSPACEEXPTIME[2O(n)]

Обновление: отвечая на дополнительный вопрос Андреаса, я полагаю, что можно доказать что-то вроде: если для всех каждый полиномиально разреженный язык в разрешим в пространстве полилога. (Быть полиномиально разреженным означает, что в языке имеется не более строк длины для всех .) Если это правда, доказательство, вероятно, будет идти в духе доказательства Хартманиса, Иммермана и Сьюэлсона, что тогда и только тогда каждый полиномиально редкий язык в содержится в . (Примечание,EXP=PSPACEcnO(logcn)poly(n)nnNE=ENPPnO(logcn)времени в пространстве полилога все еще достаточно, чтобы подразумевать .)PSPACE=EXP

Райан Уильямс
источник
1
Спасибо за хороший ответ. Теория вычислений Декстера Козена имеет красивую «унифицированную» запись для классов Руццо на странице 69: где ограничивает пространство, ограничивает время, а ограничивает чередования. Тогда а который действительно подчеркивает конструкцию. STA(f,g,h)fghNC=STA(logn,,(logn)O(1))P=STA(logn,,)
Андрас Саламон
1
Обратите внимание, что я говорю выше. Однако я думаю, что это то же самое. Машина, которая занимает полиномиальное время и пространство но выполняет только чередования может быть превращена в другую машину чередования, которая принимает только время и пространство. (Другое направление очевидно.) Идея состоит в том, чтобы добавить больше чередований, чтобы каждая полисиомально-временная экзистенциальная фаза и универсальная фаза "ускорялись", чтобы работать только за время и пространство по теореме Савича. NC=STA(logn,(logn)O(1),)O(logn)(logn)O(1)(logn)O(1)O(logn)(logn)O(1)O(logn)
Райан Уильямс
6
нам нужен какой-то скрипт greasemonkey, который автоматически связывает что-то вроде «\ NP» со входом в зоопарк.
Суреш Венкат
12

(Я видел ответ Райана, но я просто хотел представить другую точку зрения, которая была слишком длинной, чтобы вписаться в комментарий.)

В доказательстве все, что вам нужно неофициально знать о L, это то, что когда его взрывают по экспоненте, L становится PSPACE. То же самое доказательство применимо и к NL, потому что NL, взорванное экспонентой, также становится PSPACE. L=PPSPACE=EXP

Точно так же, когда NC взрывается по экспоненте, вы получаете PSPACE. Мне нравится видеть это с точки зрения схем: NC - это класс схем полиномиального размера с глубиной полилога. Когда взорван, это становится экспоненциальным размером контуров с полиномиальной глубиной. Можно показать, что это в точности PSPACE, как только будут добавлены соответствующие условия однородности. Я думаю, если NC определен с L-однородностью, то это получит PSPACE-равномерность.

Доказательство должно быть легким. В одном направлении возьмите задачу, полную PSPACE, такую ​​как TQBF, и выразите квантификаторы, используя вентили AND и OR экспоненциального размера. В другом направлении попробуйте рекурсивно пересечь контур глубины полинома. Размер стека будет полиномиальным, поэтому это можно сделать в PSPACE.

Наконец, я пришел к этому аргументу, когда увидел вопрос (и до прочтения ответа Райана), поэтому могут быть ошибки. Пожалуйста, укажите их.

Робин Котари
источник
1
Одно исправление: NC имеет схемы полиномиального размера и глубины полилога, но это все еще только полиномиальная глубина после перевода.
Райан Уильямс
@ Райан: Ты прав. Я исправлю это.
Робин Котари
1

Вот еще немного подробнее с точки зрения моделирования пространственно-временной ограниченной Чередующейся машины Тьюринга.

Предположим, что .P=NC

Поскольку , мы получаемNC=ATISP((log(n))O(1),O(log(n)))

P=ATISP((log(n))O(1),O(log(n))).

Теперь рассмотрим задачу линейного универсального моделирования которой нам дано кодирование на машине Тьюринга и входная строка длины и мы хотим знать, принимает ли не более чем за шагов.LinUMxnMxn

Мы знаем , что . Следовательно, существует постоянная (достаточно большая) такая, чтоLinUPc

()LinUATISP(logc(n),clog(n)).

В результате аргумента заполнения (немного хитрого, смотрите комментарии), мы имеем

(1)DTIME(n)ATISP(logc(n),clog(n)).

Расширяя аргумент заполнения, мы получаем

(2)DTIME(nk)ATISP(kclogc(n),kclog(n)).
(3)DTIME(2nk)ATISP(kcnkc,kcnk).

Кроме того, существуют известные результаты моделирования чередующихся пространственно-временных машин Тьюринга. В частности, мы знаем, что

ATISP(logc(n),clog(n))DSPACE(O(logc+1(n))).

Следовательно, мы (по существу) имеем следующее для всех натуральных чисел :k

(2)DTIME(nk)DSPACE(kc+1logc+1(n))
(3)DTIME(2nk)DSPACE(nk(c+1)).

Из мы получили бы этот .(3)EXP=PSPACE

==================== После мысли ===================

Важно отметить, что подразумевает для некоторой константы .P=NC

ATISP((log(n))O(1),O(log(n)))=ATISP(logc(n),O(log(n)))
c

Любые комментарии или исправления приветствуются. :)

Майкл Вехар
источник
1
@MichaelWehar Знаем ли мы при любом фиксированном ? В частности, мы знаем и, следовательно, ? NCkPSPACEkNC2PSPACENCPSPACE
T ....
1
@MichaelWehar Я не знаю, но я никогда не видел, чтобы . Фактически, комментарий в cstheory.stackexchange.com/questions/39046/… говорит, что возможно. Я разместил уточняющий запрос в cstheory.stackexchange.com/questions/40689/… . Как вы думаете, вы можете посмотреть? NCPSPACEPuniformNC1=PSPACE
T ....
1
@ Турбо Большое спасибо за добрый ответ !! Это может зависеть от вида униформы. Например, может выполняться только для логически-однородного ЧПУ. Позвольте мне подумать об этом и вернуться к вам. :)NC=ATISP((log(n))O(1),O(log(n)))
Майкл Вехар
1
@ Турбо Спасибо за продолжение !! Я действительно думаю, что вы должны прочитать определение внизу страницы 370 от: sciencedirect.com/science/article/pii/0022000081900386
Майкл Вехар
1
@ Турбо Спасибо за все ваши наблюдения! Я настоятельно рекомендую вам прочитать статью, которую я связал, потому что в ней говорится, что большинство этих понятий однородного эквивалентны. Однако в статье не рассматривается -однородная которая может отличаться, поскольку у меня нет возможности доказать, что она одинакова. NCPNC
Майкл Вехар