Qualquer polinômio difícil de contar, mas fácil de decidir?

15

Todo circuito aritmético monótono , isto é, um circuito , calcula algum polinômio multivariado F ( x 1 , , x n ) com coeficientes inteiros não negativos. Dado um polinômio f ( x 1 , , x n ) , o circuito{+,×}F(x1,,xn)f(x1,,xn)

  • Calcula se F ( um ) = f ( a ) é válido para todos uma N N ; fF(a)=f(a)aNn
  • conta se F ( a ) = f ( a ) vale para todos a { 0 , 1 } n ; fF(a)=f(a)a{0,1}n
  • decide se F ( a ) > 0 exatamente quando f ( a ) > 0 é válido para todos a { 0 , 1 } n . fF(a)>0f(a)>0a{0,1}n

Conheço polinômios explícitos (mesmo multilineares), mostrando que a diferença de tamanho de circuito "calcula / conta" pode ser exponencial. Minha pergunta diz respeito à diferença "conta / decide".f

Pergunta 1: Alguém conhece algum polinômio exponencialmente mais difícil de contar do que decidir por { + , × } -circuitos? f{+,×}

Como possível candidato, pode-se pegar o polinômio PATH cujas variáveis ​​correspondem às arestas do gráfico completo em { 1 , , n } , e cada monômio corresponde a um caminho simples do nó 1 ao nó n em K n . Esse polinômio pode ser decidido por um circuito do tamanho O ( n 3 ) implementando, digamos, o algoritmo de programação dinâmica Bellman-Ford, e é relativamente fácil mostrar que toda computação em circuito { + , × }Kn{1,,n}1nKnO(n3){+,×}PATH deve ter o tamanho . 2Ω(n)

Por outro lado, cada circuito de contagem PATH resolve o problema do caminho, isto é, conta o número de 1 Para- n caminhos no especificado pelo correspondente 0 - 1 subgráfico entrada do K n . Esse é o chamado problema # P -complete . Assim, todos "acreditamos" que PATH não pode ter nenhum circuito { + , × } contando com tamanho polinomial. O "único" problema é provar isso ... #1n01Kn#{+,×}

Posso mostrar que todo circuito conta um HP polinomial de caminho hamiltoniano relacionado requer tamanho exponencial. Monomios deste polinómio correspondem a 1 Para- n caminhos em K n contendo todos os nós. Infelizmente, a redução de # HP para # PATH da Valiant exige o cálculo da inversa da matriz de Vandermonde e, portanto, não pode ser implementada por um circuito { + , × } .{+,×}1nKn##{+,×}

Pergunta 2: Alguém viu uma redução monótona de HP para # PATH? ##

E finalmente:

Pergunta 3: Uma "versão monótona" da classe P foi considerada? #

NB Note que eu estou falando sobre uma classe muito restrita de circuitos: monótonos circuitos aritmética! Na classe dos circuitos , a pergunta 1 seria injusta de perguntar: não há limites inferiores maiores que Ω ( n log n ) para esses circuitos, mesmo quando necessário para calcular um determinado polinômio em todos os circuitos. entradas em R n , são conhecidas. Além disso, na classe de tais circuitos, um "análogo estrutural" da questão 1 - existem polinômios # P completos que podem ser decididos pelo tamanho poli { + , -{+,,×}Ω(nlogn)Rn# -circuitos? - tem uma resposta afirmativa. Tal é, por exemplo, o polinômio permanente PER = h S nn i = 1 x i , h ( i ) . {+,,×}=hSni=1nxi,h(i)

ADICIONADO: Tsuyoshi Ito respondeu à pergunta 1 com um truque muito simples. Ainda assim, as perguntas 2 e 3 permanecem em aberto. O status de contagem do PATH é interessante por si só, porque é um problema de DP padrão e porque é # P-complete.

Stasys
fonte
2
Quanto à pergunta 1, que tal adicionar 1 a um polinômio difícil de contar?
Tsuyoshi Ito 25/10
2
Suas três perguntas parecem suficientemente distintas para que sejam três perguntas separadas.
David Richerby
Receio que você não possa evitar exemplos triviais simplesmente proibindo constantes em circuitos aritméticos. Que tal adicionar x_1 +… + x_n a um polinômio difícil de contar que leva 0 na origem? (Além disso, se você proibir constantes, você não pode representar um polinômio que assume um valor diferente de zero na origem.)
Tsuyoshi Ito
'Como na "teoria #P", em "decisão" queremos dizer "existe pelo menos uma solução". E constantes não são soluções (geralmente). Você sabe, você está em uma ladeira escorregadia aqui. Considere uma contraparte #P da pergunta 1: dê um exemplo de relações R∈FNP de modo que #R seja # P-completo, mas é fácil decidir se #R (x)> 0 ou não. Podemos ficar tentados a dizer Correspondência, mas isso é um exagero. Adicionar uma solução trivial ao 3SAT funciona muito bem, e meu comentário anterior é análogo a isso. (mais)
Tsuyoshi Ito
1
@ Tsuyoshi Ito: Bem, seu truque simples (adicione a soma de todas as variáveis ​​a um polinômio difícil de contar) realmente responde à pergunta 1 (na forma como foi declarado). Você poderia colocar isso como uma resposta?
Stasys 25/10

Respostas:

7

(Estou postando meus comentários como resposta em resposta à solicitação do OP.)

Quanto à questão 1, seja f n : {0,1} n → ℕ uma família de funções cujo circuito aritmético requer tamanho exponencial. O mesmo acontece com f n +1, mas é fácil decidir f n +1 por um circuito aritmético monotônico trivial. Se você preferir evitar constantes em circuitos aritméticos monotônicos, então f n : {0,1} n → ℕ seja uma família de funções, de modo que o circuito aritmético de f n exija tamanho exponencial ef n (0,…, 0) = 0 e considere f n + x 1 +… + x n .

Tsuyoshi Ito
fonte