Circuits over sets of natural numbers

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

Circuits over natural numbers are a mathematical model used in studying computational complexity theory. They are a special case of circuits. The object is a labeled directed acyclic graph the nodes of which evaluate to sets of natural numbers, the leaves are finite sets, and the gates are set operations or arithmetic operations.

As an algorithmic problem, the problem is to find if a given natural number is an element of the output node or if two circuits compute the same set. Decidability is still an open question.

Formal definition[edit]

A natural number circuit is a circuit, i.e. a labelled directed acyclic graph of in-degree at most 2. The nodes of in-degree 0, the leaves, are finite sets of natural numbers, the labels of the nodes of in-degree 1 are −, where \overline{A}=\{x\in\mathbb{N}|x\not\in A\} and the labels of the nodes of in-degree 2 are +, ×, ∪ and ∩, where A+B=\{a+b|a\in A, b\in B\}, A\times B=\{a\times b|a\in A, b\in B\} and ∪ and ∩ with the usual set meaning.

The subset of circuits which do not use all of the possible labels are also studied.

Algorithmic problems[edit]

One can ask:

  • Is a given number n a member of the output node.
  • Is the output node empty, does it contain a specific element, is it equal to \mathbb{N}?
  • Is one node is a subset of another.

For circuits which use all the labels, all these problems are equivalent.

Proof[edit]

The first problem is reducible to the second one, by taking the intersection of the output gate and n. Indeed the new output get will be empty if and only if n was not an element of the former output gate.

The first problem is reducible to the third one, by asking if the node n is a subset of the output node.

The second problem is reducible to the first one, it suffices to multiply the output gate by 0, then 0 will be in the output gate if and only if the former output gate were not empty.

The third problem is reducible to the second one, checking if A is a subset of B is equivalent to ask if there is an element in A\cap\overline{B}.

Restrictions[edit]

Let O be a subset of {∪,∩,−,+,×}, then we call MC(O) the problem of finding if a natural number is inside the output gate of a circuit the gates' labels of which are in O, and MF(O) the same problem with the added constraint that the circuit must be a tree.

Quickly growing set[edit]

One difficulty comes from the fact that the complement of a finite set is infinite, and a computer has got only a finite memory. But even without complementation, one can create double exponential numbers. Let E_0=\{2\}, E_{i+1}=E_i\times E_i, then one can easily prove by induction on i that E_i=\{2^{2^i}\}, indeed E_0=\{2\}=\{2^1\}=\{2^{2^0}\} and by induction E_{i+1}=E_i\times E_i=\{2^{2^i}\}\times\{2^{2^i}\}=\{(2^{2^i})^2\}=\{2^{2^i\times2}\}=\{2^{2^{i+1}}\}.

And even double exponential—sized sets: let S_0=\{0,1,2\}, S_{i+1}=(S_i\times S_i)+S_i, then \{x|0<x<2^{2^i}\}\subset S_i, i.e. S_i contains the 2^{2^i} firsts number. Once again this can be proved by induction on i, it is true for S_0 by definition and let x\in\{x|0<x<2^{2^{i+1}}\}, dividing x by 2^{2^i} we see that it can be written as x=2^{2^i}\times d+r where d,r< 2^{2^i}, and by induction, 2^{2^i}, d and r are in S_i, so indeed x\in (S_i \times S_i)+ S_i.

These examples explains why addition and multiplication are enough to create problems of high complexity.

Complexity results[edit]

Membership problem[edit]

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

When the class of authorized gates is restricted, the membership problem lies inside well known complexity classes.

Complexity
O MC(O) MF(O)
∪,∩,−,+,× NEXPTIME-hard

Decidable with an oracle for the halting problem

PSPACE-hard
∪,∩,+,× NEXPTIME-complete NP-complete
∪,+,× PSPACE-complete NP-complete
∩,+,× P-hard, in co-R LOGCFL
+,× P-complete L-complete
∪,∩,−,+ 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-hard, in P L-complete
× NL-complete L-complete
∪,∩,− P-complete NC1-complete
∪,∩ P-complete L-complete
NL-complete L-complete
NL-complete L-complete

Equivalence problem[edit]

The equivalence problem asks if, given two gates of a circuit, they evaluate to the same set.

When the class of authorized gates is restricted, the equivalence problem lies inside well known complexity classes.[1] We call EC(O) and EF(O) the problem of equivalence over circuits and formulae the gates of which are in O.

Complexity
O EC(O) EF(O)
∪,∩,−,+,× NEXPTIME-hard

Decidable with an oracle for the halting problem

PSPACE-hard

Decidable with an oracle for the halting problem

∪,∩,+,× NEXPTIME-hard, in coNEXPNP ΠP2-complete
∪,+,× NEXPTIME-hard, in coNEXPNP ΠP2-complete
∩,+,× P-hard, in BPP L-hard, in LOGCFL
+,× L-hard, in LOGCFL P-hard, in coRP
∪,∩,−,+ PSPACE-complete PSPACE-complete
∪,∩,+ PSPACE-complete ΠP2-complete
∪,+ ΠP2-complete ΠP2-complete
∩,+ coC=L(2)-complete L-complete
+ C=L-complete L-complete
∪,∩,−,× PSPACE-complete PSPACE-complete
∪,∩,× PSPACE-complete ΠP2-complete
∪,× ΠP2-complete ΠP2-complete
∩,× coC=L(2)-hard, in P L-complete
× C=L-hared, in P L-complete
∪,∩,− P-complete L-complete
∪,∩ P-complete L-complete
NL-complete L-complete
NL-complete L-complete

References[edit]

  1. ^ Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers and Matthias Waldherr (2007), "Equivalence Problems for Circuits over Sets of Natural Numbers", Lecture Notes in Computer Science ((what is called "number" in bibtex) ed.) (Berlin / Heidelberg: Springer), Volume 4649/2007: 127–138, doi:10.1007/978-3-540-74510-5, ISBN 978-3-540-74509-9 

External links[edit]