Нижние оценки для размера недетерминированных цепей

17

Известно, что минимальный размер цепей, функцию четности, в точности равен . Нижняя оценка доказательства основана на методе исключения ворот.U23(N-1)

Недавно я заметил, что метод исключения затвора хорошо работает и для недетерминированных цепей, и мы можем доказать нижнюю границу для размера недетерминированных цепей, вычисляя функцию четности.U23(N-1)U2

(Это означает, что недетерминированные вычисления бесполезны для вычисления четности по цепям и не могут уменьшить размер с . Таким образом, минимальные схемы не отличаются от детерминированного случая.)U23(N-1)

Мои вопросы следующие два:

(1) Это новый результат или известный результат?

(2) В более общем смысле, существуют ли известные результаты нижних оценок для размера недетерминированных схем (включая формулы, схемы с постоянной глубиной и т. Д.) С неограниченными недетерминированными входными битами (или, другими словами, неограниченным недетерминизмом) для явного функция?

Дополнительное объяснение (27 ноября 2014 г.)

Во втором вопросе я намеревался узнать, особенно я хотел бы знать, является ли это первой нетривиальной нижней границей для размера недетерминированных схем (включая формулы, схемы с постоянной глубиной и т. Д.) С неограниченным недетерминизмом для явной функции или нет. Я знаю, что есть некоторые результаты, если недетерминизм ограничен, а именно:

[1] Хартмут Клаук: нижние границы для вычислений с ограниченным недетерминизмом. IEEE Конференция по вычислительной сложности 1998: 141-

[2] Викраман Арвинд, К.В. Субрахманям, Н.В. Винодчандран: Сложность запросов проверки программ по цепям постоянной глубины. ISAAC 1999: 123-132

Хироки Морицуми
источник

Ответы:

3

Частичный ответ на второй вопрос:

  • SО(S)S
  • В2SS/100S/100О(S)О()
  • 2N1/dN1/d

Частичный ответ на первый вопрос:

  • мне неизвестно :) было бы интересно увидеть доказательство (в частности, как можно подставить значения для экзистенциальных переменных).
Hirsch
источник
Благодарю за ваш ответ. Я также знаю некоторые факты о недетерминированных схемах. Я добавлю комментарий, чтобы прояснить второй вопрос.
Хироки Моризуми