Czy obwody AND i OR P-są kompletne?

Bramka AND & OR jest bramką, która ma dwa wejścia i zwraca ich AND oraz OR. Czy obwody wykonane tylko z bramki AND & OR, bez fanouta, mogą wykonywać dowolne obliczenia? Mówiąc ściślej, czy obszar logiczny obliczeń wielomianowych można zredukować do obwodów AND i OR?

Moja motywacja do rozwiązania tego problemu jest dość dziwna. Jak opisano tutaj , to pytanie jest ważne dla obliczeń w grze komputerowej Dwarf Fortress .

Jeśli nie rozumiem, co rozumiesz przez bramkę AND & OR, jest to w zasadzie bramka porównawcza, która bierze dwa bity wejściowe i y i wytwarza dwa bity wyjściowe x ∧ y i x ∨ y . Dwa bity wyjściowe x ∧ y i x ∨ y są w zasadzie min ( x , y ) i max ( x , y ) .$x$$y$$x\wedge y$$x\vee y$$x\wedge y$$x\vee y$$(x,y)$$(x,y)$

Obwody komparatora buduje się, łącząc razem te bramki komparatora, ale nie pozwalając na więcej wyjść poza dwoma wyjściami wytwarzanymi przez każdą bramkę . Możemy więc rysować obwody komparatora, korzystając z poniższych notacji (podobnie jak w przypadku rysowania sieci sortujących).

Możemy zdefiniować problem wartości obwodu komparatora (CCV) w następujący sposób: biorąc pod uwagę obwód komparatora z określonymi wejściami boolowskimi, określ wartość wyjściową wyznaczonego przewodu. Przyjmując zamknięcie tego problemu CCV w ramach redukcji przestrzeni logicznej, otrzymujemy klasę złożoności CC , której kompletne problemy obejmują problemy naturalne, takie jak maksymalne dopasowanie leksymalne , stabilne małżeństwo, stabilny pokój.

W tym ostatnim artykule Steve Cook, Yuval Filmus i ja pokazaliśmy, że nawet jeśli zastosujemy zamknięcie wielokrotne AC 0 , nadal otrzymamy CC tej samej klasy. Zgodnie z naszą najlepszą wiedzą w tym momencie, NL ⊆ CC ⊆ P. W naszym dokumencie przedstawiliśmy dowody, że CC i NC są nieporównywalne (tak, że CC jest właściwym podzbiorem P), podając ustawienia wyroczni, gdzie relatywizowano CC i relatywizowano NC są nieporównywalne. Daliśmy również dowód, że CC i SC są nieporównywalne.$^0$$\subseteq$$\subseteq$

(odpowiedź nie kwalifikuje się, ponieważ odnosi się do oddzielnych bramek AND, OR bez ograniczeń fan out)

Poniższy artykuł dotyczy tematu: Automaty komórkowe z większością głosów, dynamika Ising i kompletność P.

Pokazujemy, że w trzech lub więcej wymiarach systemy te mogą symulować obwody boolowskie bramek AND i OR, a zatem są P-kompletne . Oznacza to, że przewidywanie ich kroków czasowych w przyszłości jest co najmniej tak trudne, jak każdy inny problem, który wymaga czasu wielomianowego na komputerze szeregowym.

(...)

Problem Monotone Circuit Value, gdzie bramki AND i OR są dozwolone, ale bramki NIE są, nadal jest P-zupełny z następującego powodu: używając praw De Morgana (...) możemy przesuwać negacje z powrotem przez bramki, aż tylko wpływają na same dane wejściowe. W ten sposób każdy problem z wartością obwodu można przekształcić w problem z wartością obwodu monotonicznego, z zanegowaniem niektórych wejść. Ten rodzaj konwersji, od jednego problemu do drugiego, nazywa się redukcją.