Sabe-se que o tamanho mínimo dos circuitos calculam a função de paridade é exatamente igual a 3 ( n - 1 ) . A prova do limite inferior é baseada no método de eliminação do portão.
Recentemente, notei que o método de eliminação portão funciona bem também para nondeterministic -circuitos, e nós podemos provar a 3 ( n - 1 ) limite inferior para o tamanho do nondeterministic U 2 -circuitos computacionais a função de paridade.
(Isso significa que a computação não determinística é inútil para calcular a paridade por circuitos e não pode reduzir o tamanho de 3 ( n - 1 ) . Assim, os circuitos de mínimos não mudam a partir do caso determinístico).
Minhas perguntas são as duas seguintes:
(1) Esse é um resultado novo ou conhecido?
(2) De maneira mais geral, existem alguns resultados conhecidos de limites inferiores para o tamanho de circuitos não determinísticos (incluindo fórmulas, circuitos de profundidade constante e assim por diante) com bits de entrada não determinísticos ilimitados (ou, em outras palavras, não determinismo ilimitado) para um valor explícito função?
Explicação adicional (27/11/2014)
Na segunda pergunta, pretendi que gostaria de saber especialmente se esse é o primeiro limite inferior não trivial para o tamanho de circuitos não determinísticos (incluindo fórmulas, circuitos de profundidade constante e assim por diante) com não-determinismo ilimitado para uma função explícita ou não. Eu sei que existem alguns resultados se o não determinismo for limitado, como segue.
[1] Hartmut Klauck: limites mais baixos para computação com não determinismo limitado. Conferência IEEE sobre Complexidade Computacional 1998: 141-
[2] Vikraman Arvind, KV Subrahmanyam, NV Vinodchandran: A complexidade da consulta da verificação de programas por circuitos de profundidade constante. ISAAC 1999: 123-132
fonte