Do czego służą obwody z ograniczoną krawędzią?

Można mówić o treewidth z logicznego obwodu, określające go jako treewidth o „o zabarwieniu moralnym” wykresu na przewodach (wierzchołków) otrzymany w następujący sposób: przewody CONNECT $a$ i $b$ , gdy $b$ jest wyjście z bramki mające jako wejście (lub nawzajem); Podłączyć przewody a i b , gdy są one wykorzystywane jako wejścia dla samej bramy. Edycja: można równo zdefiniować szerokość obwodu jako szerokość wykresu, który go reprezentuje; jeśli użyjemy asocjatywności, aby przeredagować wszystkie bramki AND i OR, aby mieć maksymalnie dwa wachlarze, szerokość grzbietu zgodnie z jedną z definicji jest taka sama, aż do współczynnika 3 .$a$$a$$b$$3$

Istnieje co najmniej jeden problem, o którym wiadomo, że jest nierozwiązywalny ogólnie, ale możliwy do rozwiązania w obwodach boolowskich o ograniczonej szerokości poprzecznej: biorąc pod uwagę prawdopodobieństwo, że dla każdego z przewodów wejściowych zostanie ustawiona wartość 0 lub 1 (niezależnie od pozostałych), oblicz prawdopodobieństwo, że pewna bramka wyjściowa ma wartość 0 lub 1. Jest to na ogół trudność # P przez zmniejszenie np. # 2SAT, ale można ją rozwiązać w trybie PTIME w obwodach, których szerokość przyjmuje się jako mniejszą niż stała, przy użyciu algorytmu drzewa połączeń .

Moim pytaniem jest wiedzieć, czy istnieją inne problemy, poza obliczeniami probabilistycznymi, o których wiadomo, że są ogólnie trudne do rozwiązania, ale możliwe do rozwiązania w przypadku obwodów o ograniczonej szerokości poprzecznej, lub których złożoność można opisać jako funkcję wielkości obwodu, a także jego szerokości. Moje pytanie nie jest specyficzne dla przypadku logicznego; Interesują mnie również obwody arytmetyczne nad innymi półprzewodnikami. Czy widzisz jakieś takie problemy?

$k \in \mathbb{N}$$k$$k$

Tak zwane d-SDNNF to obwody spełniające warunki stosowania negacji (tylko na liściach), determinizmu (dane wejściowe do bramek OR wykluczają się wzajemnie), rozkładu (dane wejściowe do bramek AND zależą od rozłącznych zbiorów zmiennych ) i strukturalność (bramki AND dzielą zmienne w pewien ustalony sposób w obwodzie, jak opisano za pomocą drzewa v). Ta klasa była badana w zakresie kompilacji wiedzy i znana jest z tego, że cieszy się możliwym do obliczenia SAT i możliwym do zliczania modelem (ponowne obliczanie probabilistycznej oceny i liczenia), ale inne problemy były badane dla tej klasy, takie jak wyliczanie , kwantyfikacja itp.

Jednym ze sposobów wykorzystania granic na szerokości obwodu jest przekonwertowanie go na tę klasę d-SDNNF, która ma bardziej wyraźne właściwości pod względem semantyki obwodu i dla której istnieje kilka znanych wyników dotyczących wykonalności różnych zadań.