Obwody arytmetyczne o

Rozważ obwód, który przyjmuje jako liczby wejściowe w $[0,1]$ i ma bramki, które składają się z funkcji $\max(x, y)$ , $\min(x, y)$ , $1 - x$ i $\frac{x+y}{2}$ . Wyjście obwodu jest wówczas również liczbą w $[0,1]$ .

Czy ktoś wie, czy ten model lub model blisko spokrewniony został zbadany?

W szczególności próbuję rozwiązać problem satysfakcji dla tego obwodu, a mianowicie obliczenie maksymalnej wartości, którą ten obwód może osiągnąć (faktycznie osiąga maksimum, ponieważ reprezentuje funkcję ciągłą w zwartej dziedzinie).

Uwaga: moje badanie tego modelu opiera się na ważonych logikach czasowych, więc przydatne mogą być również wszystkie modele odnoszące się do tego drugiego.

arithmetic-circuits Shaull
źródło

Z pewnością ten problem jest trudny NP. (Poprzez satysfakcję: masz

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

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

\neg x \equiv 1 - x

$\neg x \equiv 1 - x$ , z którymi możesz zrobić ORAZ, LUB, i NIE.) Czy zatem masz pytanie, czy czy nie ten problem występuje w NP? Pytanie o to, czy taki obwód ma wejście, które daje wartość 1, wydaje się być w NP, ponieważ jeśli takie wejście jest takie, jest takie, które ma wartość 0/1.

Neal Young,

Jeśli niedeterministycznie wybierzemy jedną z możliwych wartości prawdy dla , gdzie są wszystkimi parami węzłów, tak że węzeł lub pojawia się w obwód zamienia się w problem programowania liniowego, który można rozwiązać w P. Zatem wersja decyzyjna pierwotnego problemu maksymalizacji jest w NP. (Jest to wariant problemu satysfakcji w logice Łukasiewicza, dlatego warto zajrzeć do rozdziału Haniková w Podręczniku matematycznej logiki rozmytej).

\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 Jeřábek

@Shaull: Pozwól, że opiszę to bardziej szczegółowo. Niech być węzły obwodu, które są min i max bramy (tutaj jest ograniczone przez rozmiar obwodu) i pozwolić i być węzłami wejściowymi bramki . Dla każdego wybierz dodatkowe ograniczenie lub . Istnieją takich wyborów. Gdy taki wybór jest ustalony, możesz uprościć obwód, zastępując przez lub

{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$ w zależności od potrzeb, przekształca się w układ równań liniowych, których zmienne są pierwotnymi zmiennymi problemu, oraz dodatkowe zmienne odpowiadające ...

Emil Jeřábek

... węzły w obwodzie. Uwzględnij nierówności stwierdzające, że dodatkowe ograniczenia są spełnione, nierówności ograniczające oryginalne zmienne do oraz nierówność stwierdzająca, że węzeł wyjściowy ma wartość . Zatem jest to program liniowy w zależności od wyboru dodatkowych ograniczeń, a obwód osiąga wartość iff istnieje wybór ograniczeń, tak że skojarzony program liniowy ma rozwiązanie.

m

$m$

[0, 1]

$[0,1]$

\geq u

$\ge u$

\geq u

$\ge u$

Emil Jeřábek

Zauważ również, że optymalną wartość programu liniowego osiąga się na wierzchołku polytopa. Oznacza to, że mianownik optymalnego rozwiązania można wyrazić jako wyznacznik macierzy wymiaru którego wpisy są liczbami całkowitymi o stałej wielkości, aw każdym wierszu znajdują się tylko niezerowe wpisy i jako takie jest ograniczony przez .

O (n)

$O(n)$

O (1)

$O(1)$

2^{O (n)}

$2^{O(n)}$

Emil Jeřábek

Odpowiedzi:

Problem spełnialności tych obwodów (biorąc pod uwagę układ i , może zadecydować, czy istnieje wejście w taki sposób, ) w NP, a zatem przez NP-zupełny Komentarz Neala Younga i odpowiedź Petera Shora. $C$ $u\in[0,1]$ $x$ $C(x)\ge u$

Możemy skonstruować niedeterministyczną redukcję problemu do programowania liniowego w następujący sposób. Niech będą wszystkimi węzłami które są bramkami min lub max (tutaj , gdzie jest rozmiarem obwodu) i niech i będą węzłami wejściowymi bramki . Dla każdego wybierz jedno z dwóch dodatkowych ograniczeń lub ( w sumie można wybrać ). Gdy taki wybór jest ustalony, możemy uprościć obwód, zastępując każdy przez lub $\{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$ odpowiednio, a powstały obwód można opisać układem równań liniowych, których zmienne są oryginalnymi zmiennymi wejściowymi obwodu, oraz dodatkowymi zmiennymi odpowiadającymi węzłom obwodu. $n$

Uwzględniamy także nierówności stwierdzające, że dodatkowe ograniczenia są spełnione, nierówności ograniczające oryginalne zmienne wejściowe do oraz nierówność stwierdzająca, że węzeł wyjściowy ma wartość . Zatem jest to program liniowy o wielkości zależności od wyboru dodatkowych ograniczeń, a obwód osiąga wartość iff istnieje wybór takich ograniczeń, że skojarzony program liniowy ma rozwiązanie. Ponieważ programowanie liniowe jest w P, pokazuje to, że problem dotyczy NP. $m$ $[0,1]$ $\ge u$ $O(n)$ $\ge u$

Zauważ również, że optymalną wartość programu liniowego osiąga się na wierzchołku polytopa. Oznacza to, że mianownik optymalnego rozwiązania można wyrazić jako wyznacznik kwadratowej macierzy wymiaru której wpisy są liczbami całkowitymi o stałej wielkości, aw każdym wierszu są tylko niezerowe wpisy , i jako takie jest ograniczony przez . $O(n)$ $O(1)$ $2^{O(n)}$

Tego rodzaju redukcje są często przydatne, aby dać górne granice złożoności satysfakcji w zdaniowych logikach rozmytych (takich jak logika Łukasiewicza) i powiązanych systemach. (W rzeczywistości pierwotny problem to niewielki wariant satysfakcji u Łukasiewicza, który odpowiadałby obwodom o zamiast ). Można znaleźć przegląd powiązanych wyników w rozdziale X Podręcznika matematycznej logiki rozmytej, t. II. $\min(1,x+y)$ $(x+y)/2$

Emil Jeřábek
źródło

Ten problem jest trudny NP.

Możesz uzyskać 3-SAT z bramkami min ( x , y ), max ( x, y ) i 1− x .

Chcemy zredukować problem 3-SAT do obwodu, dla którego można uzyskać 1, jeśli wszystkie zmienne są zadowalające, aw przeciwnym razie można osiągnąć tylko coś mniej niż 1.

Możemy wymusić, aby wszystkie zmienne miały wartość 0 lub 1, biorąc minimum wielu wyrażeń i sprawić, by te wyrażenia zawierały max ( x , 1– x ).

Teraz dla każdej klauzuli problemu 3-SAT x ∨ y ∨ z , umieszczamy wyrażenie max ( x , y , z ) na minimum.

Nie wiem, jaka jest optymalna wartość dla niezadowalającego problemu 3-SAT, ale będzie to dokładnie mniej niż 1.

Peter Shor
źródło

Tak, jak wskazano w komentarzu powyżej, twardość NP jest „łatwym kierunkiem”. W rzeczywistości, jeśli nie używasz średniej bramki, ale tylko min i max, łatwo jest pokazać, że maksymalna wartość wynosi 1, jeśli odpowiedni obwód boolowski jest zadowalający, i 1/2 w przeciwnym razie (po prostu podłączając 1/2 do wszystkich zmienne). W każdym razie problem został rozwiązany w powyższych komentarzach.

Shaull

Nie dokładnie to, o co prosiłeś, ale kontekst, w którym pojawiają się podobne obwody.

Jeśli usuniesz bramkę (o której nawet nie wspomniano w tytule!), Otrzymasz monotoniczny obwód arytmetyczny. Klasyczne monotoniczne obwody Razborova zostały rozszerzone do monotonicznych obwodów arytmetycznych (z tymi samymi wynikami) przez Pavela Pudláka, Dolne granice rozdzielczości i wycinania płaszczyzn . $1-x$

Yuval Filmus
źródło

Dzięki. Jednak w tym przypadku, jeśli usuniesz bramę , problem jest trywialny - maksymalna wartość to 1 i zostanie osiągnięta, gdy wszystkie zmienne uzyskają wartość 1.

1 - x

$1-x$

Shaull