«Правильное» условие однородности для класса Ника

9

DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/L_%28complexity%29 и определены по адресу http://en.wikipedia.org/wiki/NC_%28complexity%29
L
NCNCn

DLOGTIME кажется самым маленьким, что может сработать.
Я читал в разных местах, , хотя каждое место я обнаружил , что результаты, состояний , в которых единообразие условие использует - единообразие. Существует ли какой-либо детерминированный класс такой, что известен с -uniform и 1....известно держать? 2....LNC2
L


XLNCXNC
XL
XLизвестно, что он удерживается, а как известно, не хранится?X=L

(1, или в гораздо меньшей степени 2, может показаться, что -однородность является правильным условием)L


источник
Почему мы знаем, что L находится в неоднородном NC? Без этого мы не можем надеяться, что это будет в каком-то едином NC.
Домоторп
Ну, я нашел это на странице 235 «Энциклопедии компьютерных наук и технологий» и на www.cs.tau.ac.il/~zwick/circ-comp-new/three.ps. Тем не менее, книга - единственный результат, который я получаю, когда я ищу ссылку, на которую она указывает, и файл ps не дает доказательства. Я полагаю, я должен изучить это дальше.
3
LNC2NC
Каве
Боже, извини, хотя вопрос был о . NC1
Domotorp

Ответы:

8

Вы можете использовать для однородности и . Нет проблем, и остаются прежними и равными (для ).DLogTimeNCNC2NCkATimeSpace(O(lgkn),O(lgn))k1

Как правило, единственный случай, когда нам нужно быть более осторожным, - это случай котором нужно быть осторожным с тем, что должно быть разрешено в . Если вы используете расширенное описание схем на языке соединений, то все работает даже в случае .NC1DLogTimeNC1

Для больше на единообразии см .:

Вальтер Л. Руццо, " О сложности единой цепи ", журнал компьютерных и системных наук, вып. 22 (1981), с. 365–383.

Кава
источник
Означает ли "может использовать для единообразия" " все еще имеет место "? DLogTimeLNC2
Да это значит что DLogTime единообразный NC2 равно ATimeSpace(O(lg2n),O(lgn)) который содержит NL=NSpace(O(lgn))DSpace(O(lgn))=L,
Каве