Лог-пространство-равномерный NC содержится в детерминированном пространстве полилога (иногда пишется PolyL). Является ли лог-пространственно-равномерный RNC также в этом классе? Стандартная рандомизированная версия PolyL должна быть в PolyL, но я не вижу, чтобы (равномерный) RNC был в рандомизированном PolyL.
Трудность, которую я вижу, состоит в том, что в RNC схема может «смотреть на случайные биты» столько, сколько она хочет; случайные входы могут иметь произвольный разветвление. Но в рандомизированной версии PolyL это не значит, что вы получаете ленту со случайными битами, на которую вы можете смотреть столько, сколько захотите; скорее, вам разрешено подбрасывать монету только на каждом временном шаге.
Благодарность!
complexity-classes
randomized-algorithms
Райан О'Доннелл
источник
источник
Ответы:
Возможно , большинство людей думают , что R N C ⊆ D 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 C ⊆ N Т Я М Е ( 2 р о л у л о г ) маловероятен.
Теорема: Если Р Н С ⊆ Н Т Я М Е ( 2 р о л у л о г ) , то либо Н Е Х Р не вычислим булевых схем размера O ( 2 н / п ) (т.е. суб-MAXSIZE путем Шеннон, не имеет значения, но см. Лупанова для плотности), или Перманент не вычисляется с помощью (без деления) арифметических формул над Z квазиполиномиального размера.
Доказательство: Предположим , R N C ⊆ N 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), также очень связано с этим вопросом.
- Периклис
источник