Circuitos aritméticos com ,

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)$ , $1 - x$ e $\frac{x+y}{2}$ . 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.

arithmetic-circuits Shaull
fonte

Certamente este problema é difícil de NP. (Por meio da satisfação: você tem

x \lor y \equiv max {x, y}

$x\vee y \equiv \max\{x,y\}$ e

\neg x \equiv 1 - x

$\neg x \equiv 1 - x$ , 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

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.)

\leq 2^{n}

$\le2^n$

x \leq y

$x\le y$

x, y

$x,y$

min (x, y)

$\min(x,y)$

max (x, y)

$\max(x,y)$

Emil Jerabek

@ 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

{a_{i} : i < m}

$\{a_i:i<m\}$

m

$m$

b_{i}

$b_i$

c_{i}

$c_i$

a_{i}

$a_i$

i < m

$i<m$

b_{i} \leq c_{i}

$b_i\le c_i$

c_{i} \leq b_{i}

$c_i\le b_i$

2^{m}

$2^m$

a_{i}

$a_i$

b_{i}

$b_i$

c_{i}

$c_i$ conforme 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

... 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

$m$

[0, 1]

$[0,1]$

\geq u

$\ge u$

\geq u

$\ge u$

Emil Jerabek

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(n)$

O (1)

$O(1)$

2^{O (n)}

$2^{O(n)}$

Emil Jerabek

Respostas:

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. $C$ $u\in[0,1]$ $x$ $C(x)\ge 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 $\{a_i:i<m\}$ $C$ $m\le n$ $n$ $b_i$ $c_i$ $a_i$ $i<m$ $b_i\le c_i$ $c_i\le b_i$ $2^m$ $a_i$ $b_i$ $c_i$ conforme 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]$ $\ge u$ $O(n)$ $\ge 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)$ $2^{O(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. II $\min(1,x+y)$ $(x+y)/2$

Emil Jeřábek
fonte

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 x ∨ y ∨ z , 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

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

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 . $1-x$

Yuval Filmus
fonte

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.

1 - x

$1-x$

Shaull