정수 회로

계산 복잡성 이론에서 정수 회로는 회로에 대한 입력이 정수의 집합이고 회로의 각 게이트는 입력 세트의 설정 연산 또는 산술 연산 중 하나를 계산하는 계산의 회로 모델이다.null

알고리즘 문제로서, 가능한 질문은 주어진 정수가 출력 노드의 요소인지 또는 두 회로가 동일한 집합을 계산하는지 찾는 것이다.결정성은 여전히 공개적인 문제지만, 그러한 회로의 제한에 대한 결과가 있다.이 모델에 관한 몇 가지 질문에 대한 답을 찾는 것은 골드바흐의 추측과 같은 많은 중요한 수학적인 추측의 증거가 될 수 있다.null

고려된 집합에도 음의 정수가 포함되어 있는 경우 자연수 집합에 걸쳐 회로를 자연적으로 확장하는 것으로, 이 페이지에서는 정의가 변경되지 않는다.차이점만 언급될 것이다.null

구성원 자격 문제의 복잡성

멤버십 문제는 정수 회로 C, 회로 X에 대한 입력 및 특정 정수 n이 입력 X와 함께 제공된 경우, 정수 n이 회로 C의 출력에 있는지 여부를 결정하는 문제다.이 문제의 계산 복잡성은 회로 C에서 허용되는 관문 유형에 따라 달라진다.^[1]아래 표에는 다양한 등급의 정수회로에 대한 멤버십 문제의 계산 복잡성이 요약되어 있다.여기서 MF ${\displaystyle {}_{\mathbb{}}}$ ${\$O)는 O-formulae가 정의한 클래스를 나타내며, 최대 팬아웃 1을 가진 O-circule이다.null

복잡성

O	${\displaystyle {}_{\mathbb{}}}$ Z ${\$O)	${\displaystyle {}_{\mathbb{}}}$ Z ${\$O)
∪,∩,−,+,×	NEXPTIME-hard	PSpace-hard
∪,∩,+,×	NEXPTIME-완전	NP-완전
∪,+,×	NEXPTIME-완전	NP-완전
∩,+,×	P-하드, co-NP	L-하드, LOGCFL에서
+,×	P-하드, co-NP	L-하드, LOGCFL에서
∪,∩,−,+	PSpace-완전	PSpace-완전
∪,∩,+	PSpace-완전	NP-완전
∪,+	NP-완전	NP-완전
∩,+	CL-완전=	L-완전
+	CL-완전=	L-완전
∪,∩,−,×	PSpace-완전	PSpace-완전
∪,∩,×	PSpace-완전	NP-완전
∪,×	NP-완전	NP-완전
∩,×	(CL= ${\displaystyle }$ ${\displaystyle \oplus }$ ${\displaystyle \land \oplus }$)-hard, P.	L-완전
×	(NL-완전 ${\displaystyle \wedge }$ ${\displaystyle \land \oplus }$)-완전	L-완전
∪,∩,−	P-완전	L-완전
∪,∩	P-완전	L-완전
∪	NL-완전	L-완전
∩	NL-완전	L-완전

참조