Содержится ли равномерный РНК в пространстве полилога?

28

Лог-пространство-равномерный NC содержится в детерминированном пространстве полилога (иногда пишется PolyL). Является ли лог-пространственно-равномерный RNC также в этом классе? Стандартная рандомизированная версия PolyL должна быть в PolyL, но я не вижу, чтобы (равномерный) RNC был в рандомизированном PolyL.

Трудность, которую я вижу, состоит в том, что в RNC схема может «смотреть на случайные биты» столько, сколько она хочет; случайные входы могут иметь произвольный разветвление. Но в рандомизированной версии PolyL это не значит, что вы получаете ленту со случайными битами, на которую вы можете смотреть столько, сколько захотите; скорее, вам разрешено подбрасывать монету только на каждом временном шаге.

Благодарность!

Райан О'Доннелл
источник
4
Периклис Папаконстантину послал мне по электронной почте именно тот ответ, который я искал. Он сказал мне, что Валентин Кабанец сказал ему, что можно использовать Кабанец - Импальяццо, чтобы показать, что равномерный RNC в PolyL будет означать определенные нижние границы схемы для NEXP или для постоянного. Возможно, один из них мог бы опубликовать аргумент здесь.
Райан О'Доннелл
2
Следствие 4.13 в газете
sdcvvc
@sdvvc: Сделать ответ?
Джошуа Грохов
@ JoshuaGrochow Мы знаем, что N C = P S P A C E невозможно. Однако возможно ли R N C = P = B P P = N P = P S P A C E ? NC=PSPACERNC=P=BPP=NP=PSPACE
T ....

Ответы:

18

Возможно , большинство людей думают , что R N CD S P C E ( р о л у л о г ) (или даже , что R N C = N C ), но я скептически к этому (см вторую часть моего ответ ниже). Если Р Н С действительно содержится в D S P A C E ( р о л у л о г ) , то она также содержится в NТ Я М Е ( 2 р о л у л о г ) (более конкретно, оно находится в D T I M E ( 2 р о л у л о г ) путем перебора).

Валентин Кабанец объяснил мне следующее (фольклор) аргумент из его бумаги с Расселым Импальяццо , что объясняет , почему R N CN Т Я М Е ( 2 р о л у л о г ) маловероятен.

Теорема: Если Р Н СН Т Я М Е ( 2 р о л у л о г ) , то либо Н Е Х Р не вычислим булевых схем размера O ( 2 н / п ) (т.е. суб-MAXSIZE путем Шеннон, не имеет значения, но см. Лупанова для плотности), или Перманент не вычисляется с помощью (без деления) арифметических формул над Z квазиполиномиального размера.

Доказательство: Предположим , R N CN T I M E ( 2 р о л у л о г ) . Если у Permanent есть формула квазиполиномиального размера, то мы можем угадать и проверить такую ​​формулу для Permanent, используя квазиполиномиальный тестер полиномиального тождества времени по предположению. Это ставит в постоянных N T I M E ( 2 р О л у л о г ) .

По теореме Тоды Σ 2 также находится в N T I M E ( 2 p o l y l o g ) . По дополнению, линейная экспоненциальное время версия Х 5 также находится в N E X P . Следовательно, линейно-экспоненциальная версия Σ 5 имеет схему размера o ( 2 n / n ) (т.е. подмакс). Но с помощью простого аргумента диагонализации можно показать, что линейно-экспоненциальная версия Σ 5требует максимального размера схемы, что является противоречием (кстати, это вариант вопроса среднего уровня для курса сложности на уровне выпускника; хорошо, возможно, доказательство того, что E X P S P A C E требует схем максимального размера проще). QED.

Сейчас непопулярное направление.

Мы уже знаем, что случайное чтение много раз может сделать что-то неочевидное. Интересный пример можно найти в « Делании недетерминированности однозначным » Рейнхардтом и Аллендером (они утверждают это с точки зрения неоднородности, но в принципе речь идет об использовании случайности чтения много раз). Другой интересный пример (менее связанный с этим) - « Глубина покупки случайности для приблизительного подсчета » Эмануэле Виолы. Полагаю, все, что я говорю, это то, что я не удивлюсь, если дерандомизация R N C не будет такой, как ожидают большинство людей.

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

Кстати, понимание того, как строить PRG, дурачивающие ограниченные в пространстве модели вычислений с множественным доступом к их входу (например, линейные длины Bps), также очень связано с этим вопросом.

- Периклис

user17164
источник
msgstr "двусторонняя ошибка для нулевой ошибки".
user17164