Heltalskrets

I beräkningskomplexitetsteori är en heltalskrets en kretsmodell för beräkning där ingångarna till kretsen är uppsättningar av heltal och varje grind i kretsen beräknar antingen en uppsättningsoperation eller en aritmetisk operation på dess ingångsuppsättningar.

Som ett algoritmiskt problem är de möjliga frågorna att ta reda på om ett givet heltal är ett element i utgångsnoden eller om två kretsar beräknar samma mängd. Beslutbarheten är fortfarande en öppen fråga, men det finns resultat på begränsning av dessa kretsar. Att hitta svar på några frågor om denna modell kan tjäna som ett bevis på många viktiga matematiska gissningar, som Goldbachs gissningar .

Det är en naturlig förlängning av kretsarna över mängder av naturliga tal när den betraktade mängden även innehåller negativa heltal, definitionerna, som inte ändras, kommer inte att upprepas på denna sida. Endast skillnaderna kommer att nämnas.

Komplexiteten i medlemskapsproblemet

Medlemskapsproblemet är problemet att bestämma, givet en heltalskrets C , en ingång till kretsen X och ett specifikt heltal n , huruvida heltal n är i utgången av kretsen C när det förses med ingång X. Beräkningskomplexiteten för detta problem beror på typen av grindar som tillåts i kretsen C. Tabellen nedan sammanfattar beräkningskomplexiteten hos medlemskapsproblemet för olika klasser av heltalskretsar. Här betecknar MF $_{\mathbb {Z} }$ (O) de klasser som definieras av O-formler, som är O-kretsar med maximal fan-out 1.

Komplexitet

O	MC $_{\mathbb {Z} }$ (O)	MF $_{\mathbb {Z} }$ (O)
∪,∩,−,+,×	NEXPTIME -hårt	PSPACE -hårt
∪,∩,+,×	NEXPTIME -klar	NP-komplett
∪,+,×	NEXPTIME -klar	NP-komplett
∩,+,×	P -hård, i sam-NP	L -hårt, i LOGCFL
+,×	P -hård, i sam-NP	L -hårt, i LOGCFL
∪,∩,−,+	PSPACE -komplett	PSPACE -komplett
∪,∩,+	PSPACE -komplett	NP-komplett
∪,+	NP-komplett	NP-komplett
∩,+	C=L-komplett	L -komplett
+	C=L-komplett	L -komplett
∪,∩,−,×	PSPACE -komplett	PSPACE -komplett
∪,∩,×	PSPACE -komplett	NP-komplett
∪,×	NP-komplett	NP-komplett
∩,×	(C=L $\land \oplus$ L)-hårt, i P	L -komplett
×	( NL -komplett $\land \oplus$ L)-komplett	L -komplett
∪,∩,−	P -komplett	L -komplett
∪,∩	P -komplett	L -komplett
∪	NL -komplett	L -komplett
∩	NL -komplett	L -komplett