Недетерминированная логическая схема имеет, помимо обычных входов , набор «недетерминированных» входов . Недетерминированная схема принимает вход если существует такой, что выход схемы включен . Аналогично (класс языков, разрешимых схемами полиномиального размера), можно определить как класс языков, разрешимых недетерминированными схемами полиномиального размера. Широко распространено мнение, что недетерминированные схемы являются более мощными, чем детерминированные схемы, в частностиу = ( у 1 , ... , у м ) С х у 1 ( х , у ) Р / р о л у Н Р / р о л у N P ⊂ P / р о л у подразумевают, что полиномиальная иерархия разрушается.
Есть ли в литературе явный (и безусловный) пример, показывающий, что недетерминированные схемы являются более мощными, чем детерминированные схемы?
В частности, знаете ли вы семейство функций вычисляемых недетерминированными схемами размера , но не вычисляемых детерминированными схемами размера ?
источник
Ответы:
Если у этой проблемы нет прогресса, у меня есть ответ.
-
Я также рассматривал эту проблему со времен моей статьи COCOON'15 (до вашего вопроса).
Теперь у меня есть доказательство стратегии, и это сразу дает следующую теорему: Существует булева функция такая , что недетерминирован U 2 -circuit сложность е самое большее 2 п + о ( п ) и детерминированный U 2 -circuit сложность f составляет 3 n - o ( n ) .е U2 е 2 n + o ( n ) U2 е 3 n - o ( n )
Я прошу прощения, что я не написал газету. Эскиза доказательства ниже может быть достаточно, чтобы объяснить мою стратегию доказательства. Я стремлюсь написать статью с большим количеством результатов к крайнему сроку STACS (1 октября).
[Эскиз доказательства]
Пустье= ∨N√- 1я = 0пгя т уN√( хN√⋅ я + 1, ... , ХN√⋅ я + н√)
Детерминированное доказательство нижней границы основано на стандартном методе исключения гейта с небольшой модификацией.
Недетерминированное доказательство верхней границы является конструкцией такой недетерминированной схемы.
источник