Известно, что минимальный размер цепей, функцию четности, в точности равен . Нижняя оценка доказательства основана на методе исключения ворот.
Недавно я заметил, что метод исключения затвора хорошо работает и для недетерминированных цепей, и мы можем доказать нижнюю границу для размера недетерминированных цепей, вычисляя функцию четности.
(Это означает, что недетерминированные вычисления бесполезны для вычисления четности по цепям и не могут уменьшить размер с . Таким образом, минимальные схемы не отличаются от детерминированного случая.)
Мои вопросы следующие два:
(1) Это новый результат или известный результат?
(2) В более общем смысле, существуют ли известные результаты нижних оценок для размера недетерминированных схем (включая формулы, схемы с постоянной глубиной и т. Д.) С неограниченными недетерминированными входными битами (или, другими словами, неограниченным недетерминизмом) для явного функция?
Дополнительное объяснение (27 ноября 2014 г.)
Во втором вопросе я намеревался узнать, особенно я хотел бы знать, является ли это первой нетривиальной нижней границей для размера недетерминированных схем (включая формулы, схемы с постоянной глубиной и т. Д.) С неограниченным недетерминизмом для явной функции или нет. Я знаю, что есть некоторые результаты, если недетерминизм ограничен, а именно:
[1] Хартмут Клаук: нижние границы для вычислений с ограниченным недетерминизмом. IEEE Конференция по вычислительной сложности 1998: 141-
[2] Викраман Арвинд, К.В. Субрахманям, Н.В. Винодчандран: Сложность запросов проверки программ по цепям постоянной глубины. ISAAC 1999: 123-132
источник