Circuitos aritméticos com ,

12

Considere um circuito que recebe como números de entrada em [0,1] e possui portas que consistem nas funções max(x,y) , min(x,y) , 1x e x+y2 . A saída do circuito também é um número em [0,1] .

Alguém sabe se este modelo, ou um modelo estreitamente relacionado, foi estudado?

Especificamente, estou tentando resolver o problema de satisfação deste circuito, ou seja, calcular o valor máximo que pode ser alcançado por esse circuito (ele realmente atinge o máximo, pois representa uma função contínua em um domínio compacto).

Observação: meu estudo desse modelo é por meio de lógicas temporais ponderadas; portanto, qualquer modelo relacionado a esse último também pode ser útil.

Shaull
fonte
5
Certamente este problema é difícil de NP. (Por meio da satisfação: você tem xymax{x,y} e ¬x1x , com o qual você pode fazer AND, OR e NOT.) Portanto, sua pergunta é se ou não esse problema está no NP? A questão da decisão de saber se esse circuito possui uma entrada que produz o valor 1 parece estar em NP, pois, se houver uma entrada, existe uma que seja 0/1.
Neal Young
3
Se escolhermos não deterministicamente um dos possíveis valores de verdade para , em que são todos pares de nós, de modo que um nó ou apareça em No circuito, isso se transforma em um problema de programação linear, solucionável em P. Portanto, a versão de decisão do problema de maximização original está em NP. (Esta é uma variante do problema satisfiability na lógica Łukasiewicz, de modo que você pode querer olhar para o capítulo de Haniková no Handbook of Mathematical Fuzzy Logic para obter informações relacionadas.)2nxyx,ymin(x,y)max(x,y)
Emil Jerabek
5
@ Shaull: Deixe-me descrevê-lo em mais detalhes. Seja os nós do circuito que são portas mínimas ou máximas (aqui é limitado pelo tamanho do circuito) e e sejam os nós de entrada do gate . Para cada , escolha uma restrição adicional ou . Existem dessas escolhas. Quando essa escolha é corrigida, você pode simplificar o circuito substituindo por ou{ai:i<m}mbiciaii<mbicicibi2maibiciconforme o caso, portanto, ele se transforma em um sistema de equações lineares cujas variáveis são as variáveis originais do problema, e variáveis adicionais correspondentes a ...
Emil Jerabek
4
... nós no circuito. Inclua desigualdades indicando que as restrições extras são atendidas, desigualdades limitando as variáveis ​​originais a e uma desigualdade indicando que o nó de saída tem valor . Então este é um programa linear, dependendo da escolha das restrições extras, e o circuito atinge valor se houver uma escolha das restrições, de modo que o programa linear associado tenha uma solução. m[0,1]uu
Emil Jerabek
5
Observe também que o valor ideal de um programa linear é atingido em um vértice do politopo. Isso significa que o denominador da solução ótima pode ser expresso como determinante de uma matriz da dimensão cujas entradas são números inteiros de tamanho constante e existem apenas entradas diferentes de zero em cada linha e, como tal, é limitado por . O(n)O(1)2O(n)
Emil Jerabek

Respostas:

12

O problema de satisfação desses circuitos (ou seja, dados os circuitos e , decide se existe uma entrada tal que ) esteja em NP e, portanto, NP-completo por Comentário de Neal Young e resposta de Peter Shor.Cu[0,1]xC(x)u

Podemos construir uma redução não determinística do problema para programação linear da seguinte maneira. Seja todos os nós de que são portas mínimas ou máximas (aqui , onde é o tamanho do circuito) e e sejam os nós de entrada do portão . Para cada , escolha uma das duas restrições adicionais ou (existem opções possíveis no total). Quando essa escolha é corrigida, podemos simplificar o circuito substituindo cada por ou{ai:i<m}Cmnnbiciaii<mbicicibi2maibiciconforme apropriado, e o circuito resultante pode ser descrito por um sistema de equações lineares cujas variáveis ​​são as variáveis ​​de entrada originais do circuito e variáveis ​​adicionais correspondentes aos nós do circuito.n

Também incluímos desigualdades declarando que as restrições extras são atendidas, desigualdades limitando as variáveis ​​de entrada originais a e uma desigualdade declarando que o nó de saída tem valor . Então este é um programa linear de tamanho dependendo da escolha das restrições extras, e o circuito obtém valor se houver uma escolha das restrições, de modo que o programa linear associado tenha uma solução. Como a programação linear está em P, isso mostra que o problema está em NP.m[0,1]uO(n)u

Observe também que o valor ideal de um programa linear é atingido em um vértice do politopo. Isso significa que o denominador da solução ótima pode ser expresso como determinante de uma matriz quadrada da dimensão cujas entradas são números inteiros de tamanho constante e existem apenas entradas diferentes de zero em cada linha e, como tal, é delimitada por .O(n)O(1)2O(n)

Geralmente, reduções desse tipo são úteis para fornecer limites superiores à complexidade da satisfação em lógicas nebulosas proposicionais (como a lógica asukasiewicz) e sistemas relacionados. (De fato, o problema original é uma variante menor de satisfação em Łukasiewicz, que corresponderia a circuitos com vez de ) Uma visão geral dos resultados relacionados pode ser encontrada no capítulo X do Handbook of Mathematics Fuzzy Logic, vol. IImin(1,x+y)(x+y)/2

Emil Jeřábek
fonte
4

Este problema é difícil de NP.

Você pode obter 3-SAT com os portões min ( x , y ), max ( x, y ) e 1− x .

O que queremos é reduzir um problema de 3-SAT a um circuito para o qual você pode obter 1 se todas as variáveis ​​forem satisfatórias e você só pode obter algo estritamente menor que 1 caso contrário.

Podemos forçar todas as variáveis ​​a serem 0 ou 1, usando um mínimo de muitas expressões, e fazer com que essas expressões incluam max ( x , 1− x ).

Agora, para cada cláusula no problema 3-SAT xyz , colocamos a expressão max ( x , y , z ) no mínimo.

Não sei qual é o valor ideal para um problema 3-SAT não satisfatório, mas será estritamente menor que 1.

Peter Shor
fonte
2
Sim, a dureza NP é a "direção fácil", como apontado em um comentário acima. De fato, se você não usar o gate médio, mas apenas min e max, é fácil mostrar que o valor máximo é 1 se o circuito booleano correspondente for satisfatório e 1/2 caso contrário (simplesmente conectando 1/2 a todos as variáveis). De qualquer forma, o problema foi resolvido nos comentários acima.
Shaull
1

Não é exatamente o que você pediu, mas um contexto em que circuitos semelhantes aparecem.

Se você remover o portão (que nem é mencionado no título!), O que você obtém é um circuito aritmético monótono. Os limites inferiores clássicos de Razborov do circuito monótono foram estendidos a circuitos aritméticos monotônicos (com os mesmos resultados) por Pavel Pudlák, limites inferiores para resolução e provas de planos de corte .1x

Yuval Filmus
fonte
3
Obrigado. Neste caso, no entanto, se você remover o portão, então o problema é trivial - o valor máximo é 1 e é alcançado quando todas as variáveis obter o valor 1.1x
Shaull