Integer circuit

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Integer circuits is a mathematical model used in studying computational complexity theory. It is a special case of circuit, the object is a labeled directed acyclic graph the nodes of which evaluate to sets of integers, the leaves are finite sets, and the gates are set operations or arithmetic operations.

As an algorithmic problem, the possible questions are to find if a given integer is an element of the output node or if two circuits compute the same set. The decidability is still an open question, but there are results on restriction of thoses circuits. Finding answers to some questions about this model could serve as a proof to many important mathematical conjectures, like Goldbach's conjecture.

It is a natural extension of the circuits over sets of natural numbers when the considered set contains also negative integers, the definitions, which does not change, will not be repeated on this page. Only the differences will be mentioned.

Complexity results[edit]

Membership problem[edit]

The membership problem ask if, given an element n and a circuit, if n is in the output gate of the circuit.

When the class of authorized gate is restricted, the membership problem lay inside well-known complexity classes.[1]

O MC_{\mathbb Z}(O) MF_{\mathbb Z}(O)
∪,∩,−,+,× NEXPTIME-hard PSPACE-hard
∪,∩,+,× NEXPTIME-complete NP-complete
∪,+,× NEXPTIME-complete NP-complete
∩,+,× P-hard, in co-NP L-hard, in LOGCFL
+,× P-hard, in co-NP L-hard, in LOGCFL
∪,∩,−,+ PSPACE-complete PSPACE-complete
∪,∩,+ PSPACE-complete NP-complete
∪,+ NP-complete NP-complete
∩,+ C=L-complete L-complete
+ C=L-complete L-complete
∪,∩,−,× PSPACE-complete PSPACE-complete
∪,∩,× PSPACE-complete NP-complete
∪,× NP-complete NP-complete
∩,× (C=L\land\oplusL)-hard, in P L-complete
× (NL-complete\land\oplusL)-complete L-complete
∪,∩,− P-complete L-complete
∪,∩ P-complete L-complete
NL-complete L-complete
NL-complete L-complete


  1. ^ Stephen Travers (2006), "The complexity of membership problems for circuits over sets of integers", Theoretical Computer Science (1–3 ed.) (Essex, UK: Elsevier Science Publishers Ltd) 369 (1): 211–229, doi:10.1016/j.tcs.2006.08.017, ISSN 0304-3975