Obwód całkowity

W teorii złożoności obliczeniowej obwód liczb całkowitych jest obwodowym modelem obliczeń , w którym dane wejściowe do obwodu są zbiorami liczb całkowitych , a każda bramka obwodu oblicza operację na zbiorze lub operację arytmetyczną na swoich zestawach wejściowych.

Jako problem algorytmiczny możliwe są pytania, czy dana liczba całkowita jest elementem węzła wyjściowego, czy też dwa obwody obliczają ten sam zbiór. Rozstrzygalność jest nadal kwestią otwartą, ale są wyniki dotyczące ograniczenia tych obwodów. Znalezienie odpowiedzi na niektóre pytania dotyczące tego modelu może posłużyć jako dowód wielu ważnych hipotez matematycznych, takich jak hipoteza Goldbacha .

Jest to naturalne rozszerzenie obwodów po zbiorach liczb naturalnych , gdy rozpatrywany zbiór zawiera również liczby całkowite ujemne, definicje, które się nie zmieniają, nie będą powtarzane na tej stronie. Wymienione zostaną tylko różnice.

Złożoność problemu członkostwa

Problem przynależności to problem decydowania, biorąc pod uwagę obwód całkowity C , wejście do obwodu X i określoną liczbę całkowitą n , czy liczba całkowita n jest na wyjściu obwodu C , gdy jest wyposażony w wejście X . Złożoność obliczeniowa tego problemu zależy od typu bramek dozwolonych w obwodzie C. Poniższa tabela podsumowuje złożoność obliczeniową problemu członkostwa dla różnych klas obwodów liczb całkowitych. Tutaj, MF ${\ Displaystyle _ {\ mathbb {Z}}}$ (O) oznacza klasy zdefiniowane przez O-formuły, które są O-obwodami z maksymalnym rozrzutem 1.

Złożoność

O	MC ${\ Displaystyle _ {\ mathbb {Z}}}$ (O)	MF ${\ Displaystyle _ {\ mathbb {Z}}}$ (O)
∪,∩,-,+,×	NEXPTIME - trudne	PSPACE - trudne
∪,∩,+,×	NEXPTIME - ukończone	NP-zupełny
∪,+,×	NEXPTIME - ukończone	NP-zupełny
∩,+,×	P -twarde, w co-NP	L -twarde, w LOGCFL
+,×	P -twarde, w co-NP	L -twarde, w LOGCFL
∪,∩,-,+	PSPACE -kompletne	PSPACE -kompletne
∪,∩,+	PSPACE -kompletne	NP-zupełny
∪,+	NP-zupełny	NP-zupełny
∩,+	C=L-kompletny	L -kompletny
+	C=L-kompletny	L -kompletny
∪,∩,-,×	PSPACE -kompletne	PSPACE -kompletne
∪, ∩, ×	PSPACE -kompletne	NP-zupełny
∪, ×	NP-zupełny	NP-zupełny
∩, ×	( C = L ${\ Displaystyle \ land \ oplus}$ L) - twardo, w P.	L -kompletny
×	( NL -kompletny ${\ Displaystyle \ ziemia \ oplus}$ L) - kompletny	L -kompletny
∪,∩,-	P -kompletne	L -kompletny
∪, ∩	P -kompletne	L -kompletny
∪	NL -kompletny	L -kompletny
∩	NL -kompletny	L -kompletny