Limites inferiores para o tamanho de circuitos não determinísticos

17

Sabe-se que o tamanho mínimo dos circuitos calculam a função de paridade é exatamente igual a 3 ( n - 1 )você23(n-1 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.você23(n-1 1)você2

(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 )você23(n-1 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

Hiroki Morizumi
fonte

Respostas:

3

Uma resposta parcial para a segunda pergunta:

  • limites inferiores exponenciais para funções explícitas para qualquer classe que contenha 3-CNF não se convertem em limites inferiores exponenciais para não-determinismo ilimitado, porque é possível transformar qualquer circuito do tamanho em um 3-CNF não-determinístico do tamanho O ( S ) com não-determinismo S ,SO(S)S
  • mesmo que você queira um não determinismo menor que S, isso ainda é possível se a função for calculada por uma fórmula (por exemplo, paridade), porque é possível dividir essa fórmula do tamanho S em, digamos, peças do S / 100 introduzindo S / 100 novas variáveis ​​e a fórmula resultante será do tamanho O ( S ) (embora a constante no O ( ) seja grande),B2SS/100S/100O(S)O()
  • para um não-determinismo limitado (mas crescente), é possível, é claro, usar bons e velhos limites (por exemplo, o limite inferior exponencial de Hastad para a paridade permanece exponencial se o não-determinismo for muito menor que n 1 / d : apenas enumere tudo o possível bits para o não-determinismo e faça uma grande OR das fórmulas resultantes).2n1 1/dn1 1/d

Uma resposta parcial à primeira pergunta:

  • não sou conhecido por mim :) seria interessante ver a prova (em particular, como você pode substituir valores pelas variáveis ​​existenciais).
Hirsch
fonte
Obrigado pela sua resposta. Também conheço alguns fatos sobre circuitos não determinísticos. Vou adicionar um comentário para esclarecer a segunda pergunta.
Hiroki Morizumi