Пример, демонстрирующий силу недетерминированных цепей

17

Недетерминированная логическая схема имеет, помимо обычных входов , набор «недетерминированных» входов . Недетерминированная схема принимает вход если существует такой, что выход схемы включен . Аналогично (класс языков, разрешимых схемами полиномиального размера), можно определить как класс языков, разрешимых недетерминированными схемами полиномиального размера. Широко распространено мнение, что недетерминированные схемы являются более мощными, чем детерминированные схемы, в частностиу = ( у 1 , ... , у м ) С х у 1 ( х , у ) Р / р о л у Н Р / р о л у N P P / р о л уx=(x1,,xn)y=(y1,,ym)Cxy1(x,y)P/polyNP/polyNPP/poly подразумевают, что полиномиальная иерархия разрушается.

Есть ли в литературе явный (и безусловный) пример, показывающий, что недетерминированные схемы являются более мощными, чем детерминированные схемы?

В частности, знаете ли вы семейство функций вычисляемых недетерминированными схемами размера , но не вычисляемых детерминированными схемами размера ?{fn}n>0cn(c+ϵ)n

Густав Норд
источник
4
Я не думаю, что такая семья известна. Вот недавняя статья, посвященная изучению недетерминированных схем: arxiv.org/abs/1504.06731 Я помню, что перед публикацией статьи Хироки задавал подобный вопрос здесь
Александр Сергеевич Куликов
2
Благодарю. Я предполагаю, что вопрос, на который вы ссылаетесь, заключается в следующем: cstheory.stackexchange.com/q/25736, который связан, но запрашивает нижние оценки недетерминированной сложности схемы.
Густав Норд
3
Одним из важных свойств недетерминированных схем является то, что они всегда могут быть преобразованы в эквивалентные схемы глубины 2 путем добавления большего количества недетерминированных входов, используя те же идеи, что и при переходе от CircuitSAT к SAT. В частности, это означает, что недетерминированные схемы глубины 2 могут вычислять четность n битов в полиномиальном размере, в то время как детерминированные схемы глубины 2, вычисляющие четность, должны иметь размер 2 ^ n-1.
Или Меир
1
Хорошая точка зрения! Особенно в связи с упомянутым выше результатом Хироки, что недетерминированная сложность схемы четности равна 3 (n-1), что равно детерминированной сложности схемы четности.
Густав Норд,
1
Случай формул Деморгана аналогичен схемам глубины 2, упомянутым выше. Недетерминированные формулы DeMorgan могут вычислить четность n битов в линейном размере, используя те же идеи, что и схемы глубины 2, в то время как детерминированные формулы DeMorgan требуют квадратичного размера по теореме Храпченко.
Хироки

Ответы:

4

Если у этой проблемы нет прогресса, у меня есть ответ.

-

Я также рассматривал эту проблему со времен моей статьи COCOON'15 (до вашего вопроса).

Теперь у меня есть доказательство стратегии, и это сразу дает следующую теорему: Существует булева функция такая , что недетерминирован U 2 -circuit сложность е самое большее 2 п + о ( п ) и детерминированный U 2 -circuit сложность f составляет 3 n - o ( n ) .еU2е2N+о(N)U2е3N-о(N)

Я прошу прощения, что я не написал газету. Эскиза доказательства ниже может быть достаточно, чтобы объяснить мою стратегию доказательства. Я стремлюсь написать статью с большим количеством результатов к крайнему сроку STACS (1 октября).

[Эскиз доказательства]

Пусть езнак равноязнак равно0N-1пaряTYN(ИксNя+1,...,ИксNя+N)

Детерминированное доказательство нижней границы основано на стандартном методе исключения гейта с небольшой модификацией.

Недетерминированное доказательство верхней границы является конструкцией такой недетерминированной схемы.

  1. пaряTYNо(N)
  2. N2N+о(N)
  3. Объедините две цепи.
Хироки Морицуми
источник
Что-то не так с границами. Недетерминированная сложность не может быть больше, чем детерминированная сложность.
Эмиль Йержабек поддерживает Монику
Спасибо за ваш ответ, именно то, что я искал!
Густав Норд