 Circuits over sets of natural numbers

Circuits over natural numbers 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 natural numbers, the leaves are finite sets, and the gates are set operations or arithmetic operations.
As an algorithmic problem, the possible question are to find if a given natural number is an element is in 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 those circuits. Finding answers to some questions about this model could serve as a proof to many important mathematical conjectures, like Goldbach's conjecture.
Contents
Formal definition
An natural number circuit is a circuit, i.e. a labelled directed acyclic graph of indegree at most 2. The nodes of indegree 0, the leaves, are finite sets of natural numbers, the labels of the nodes of indegree 1 are −, where and the labels of the nodes of indegree 2 are +, × and ∪, where , 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
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 ?
 Is one node is a subset of another.
For circuits which use all the labels, all these problems are equivalent. They are all equivalent if we can use any labels for the gates.
Proof
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 .
Restrictions
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.
Examples
 The set of numbers greater than n is . In particular ?
 The set of prime numbers with 0 and 1, PRIME' is the complement of the numbers who are multiple of 2 natural numbers greater than 2, so it is
 The set of prime numbers, PRIME is then PRIME', the elements of PRIME' greater than 2.
 The set of EVEN numbers is .
Goldbach's conjecture asks if there is an even number greater than 2 which is not the sum of two prime numbers, it is natural to rephrase this question by asking if there is an element in .
Quickly growing set
One difficulty come from the fact that the complement of a finite set is infinite, and computer has got only a finite memory. But even without complementation, one can create double exponential number. Let , then one can easily prove by induction on i that , indeed and by induction .
And even double exponential—sized sets: let , then , i.e. S_{i} contains the firsts number. Once again this can be proved by induction on i, it is true for S_{0} by definition and let , dividing x by we see it can be written as where , and by induction, and r are in S_{i}, so indeed .
Those examples explains why addition and multiplication are enough to create problem of high complexity.
Complexity results
Membership problem
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.
Complexity O MC(O) MF(O) ∪,∩,−,+,× NEXPTIMEhard Decidable with an oracle for the halting problem
PSPACEhard ∪,∩,+,× NEXPTIMEcomplete NPcomplete ∪,+,× PSPACEcomplete NPcomplete ∩,+,× Phard, in coR LOGCFL +,× Pcomplete Lcomplete ∪,∩,−,+ PSPACEcomplete PSPACEcomplete ∪,∩,+ PSPACEcomplete NPcomplete ∪,+ NPcomplete NPcomplete ∩,+ Lcomplete + Lcomplete ∪,∩,−,× PSPACEcomplete PSPACEcomplete ∪,∩,× PSPACEcomplete NPcomplete ∪,× NPcomplete NPcomplete ∩,× P Lcomplete × NLcomplete Lcomplete ∪,∩,− Pcomplete NC^{1}complete ∪,∩ Pcomplete Lcomplete ∪ NLcomplete Lcomplete ∩ NLcomplete Lcomplete Equivalence problem
The equivalence problem ask if, given two gates of a circuits, they evaluate to the same set.
When the class of authorized gate is restricted, the equivalence problem lay inside well known complexity classes^{[1]}. We call EC(O) and EF(O) the problem of equivalence over circuits and formulae the gate of which are in O.
Complexity O EC(O) EF(O) ∪,∩,−,+,× NEXPTIMEhard Decidable with an oracle for the halting problem
PSPACEhard Decidable with an oracle for the halting problem
∪,∩,+,× NEXPTIMEhard, in coNEXP^{NP} Π^{P}_{2}complete ∪,+,× NEXPTIMEhard, in coNEXP^{NP} Π^{P}_{2}complete ∩,+,× Phard, in BPP Lhard, in LOGCFL +,× Lhard, in LOGCFL Phard, in coRP ∪,∩,−,+ PSPACEcomplete PSPACEcomplete ∪,∩,+ PSPACEcomplete Π^{P}_{2}complete ∪,+ Π^{P}_{2}complete Π^{P}_{2}complete ∩,+ coLcomplete + Lcomplete ∪,∩,−,× PSPACEcomplete PSPACEcomplete ∪,∩,× PSPACEcomplete Π^{P}_{2}complete ∪,× Π^{P}_{2}complete Π^{P}_{2}complete ∩,× coP Lcomplete × P Lcomplete ∪,∩,− Pcomplete Lcomplete ∪,∩ Pcomplete Lcomplete ∪ NLcomplete Lcomplete ∩ NLcomplete Lcomplete References
 ^ 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 (Berlin / Heidelberg: Springer) Volume 4649/2007: 127–138, doi:10.1007/9783540745105, ISBN 9783540745099, http://www.springerlink.com/content/c007kk787054v746/
 Travers, Stephen (2006), The Complexity of Membership Problems for Circuits over Sets of Natural Numbers, 389, Theoretical Computer Science, pp. 211–229, ISSN 03043975, http://portal.acm.org/citation.cfm?id=1238761
 Pierre McKenzie and Klaus W. Wagner (2003), "The Complexity of Membership Problems for Circuits over Sets of Natural Numbers", Lecture Notes In Computer Science (SpringerVerlag) 2607: 571–582, ISBN 3540006230, http://portal.acm.org/citation.cfm?id=646517.696311
External links
 Pierre McKenzie, The complexity of circuit evaluation over the natural numbers
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… … Wikipedia
Matroid — In combinatorics, a branch of mathematics, a matroid ( /ˈmeɪ … Wikipedia
Boolean algebra — This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). Boolean algebra, as developed in 1854 by George Boole in his book An Investigation of the Laws of Thought,[1] is a… … Wikipedia
telephone — telephoner, n. /tel euh fohn /, n., v., telephoned, telephoning. n. 1. an apparatus, system, or process for transmission of sound or speech to a distant point, esp. by an electric device. v.t. 2. to speak to or summon (a person) by telephone. 3.… … Universalium
Complex number — A complex number can be visually represented as a pair of numbers forming a vector on a diagram called an Argand diagram, representing the complex plane. Re is the real axis, Im is the imaginary axis, and i is the square root of –1. A complex… … Wikipedia
automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… … Universalium
Matrix (mathematics) — Specific elements of a matrix are often denoted by a variable with two subscripts. For instance, a2,1 represents the element at the second row and first column of a matrix A. In mathematics, a matrix (plural matrices, or less commonly matrixes)… … Wikipedia
number game — Introduction any of various puzzles and games that involve aspects of mathematics. Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… … Universalium
photography, technology of — Introduction equipment, techniques, and processes used in the production of photographs. The most widely used photographic process is the black and white negative–positive system (Figure 1 >). In the camera the lens projects an image of… … Universalium
Boolean algebra (introduction) — Boolean algebra, developed in 1854 by George Boole in his book An Investigation of the Laws of Thought , is a variant of ordinary algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that… … Wikipedia