Orlicz–Pettis theorem

2013-12-14T22:18:00Z

136.152.142.157: /* Orlicz–Pettis theorem for normed spaces */

'''[[Circuit (computer theory)|Circuit]]s over [[natural number]]s''' is a mathematical model used in studying [[computational complexity theory]]. It is a special case of [[circuit (computer theory)|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 [[algorithm]]ic 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]].

== Formal definition ==
An natural number circuit is a [[circuit complexity|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 <math>\overline{A}=\{x\in\mathbb{N}|x\not\in A\}</math> and the labels of the nodes of in-degree 2 are +, ×, ∪ and ∩, where <math>A+B=\{a+b|a\in A, b\in B\}</math>, <math>A\times B=\{a\times b|a\in A, b\in B\}</math> and ∪ and ∩ with the usual [[Set (mathematics)|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 <math>\mathbb{N}</math>?
*Is one node is a subset of another.

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

==== 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 <math>A\cap\overline{B}</math>.

=== 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 (graph theory)|tree]].

== Examples ==
* The set of numbers greater than ''n'' is <math>\overline{\{0,\dots,n\}}</math>. In particular <math>\mathbb{N}=\overline{\{\}}</math>
* 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 <math>\overline{\overline{\{0,1\}}\times \overline{\{0,1\}}}</math>
* The set of prime numbers, ''PRIME'' is then PRIME'<math>\cap \overline{\{0,1\}}</math>, the elements of PRIME' greater than 2.
* The set of ''EVEN'' numbers is <math>\mathbb{N}\times \{2\}</math>.

[[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 <math>EVEN\cap \overline{\{2\}}\cap \overline{PRIMES+PRIMES}</math>.

=== 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 function|double exponential]] number. Let <math>E_0=\{2\}, E_{i+1}=E_i\times E_i</math>, then one can easily prove by induction on <math>i</math> that <math>E_i=\{2^{2^i}\}</math>, indeed <math>E_0=\{2\}=\{2^1\}=\{2^{2^0}\}</math> and by induction <math>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}}\}</math>.

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

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.

{| class="wikitable" style="text-align:center; width:80%;"
|+ Complexity
|-
! scope=col | O
! scope=col | MC(O)
! scope=col | MF(O)
|-
! scope=row | ∪,∩,−,+,×
| [[NEXPTIME]]-hard
Decidable with an [[oracle machine|oracle]] for the [[halting problem]]
| [[PSPACE]]-hard
|-
! scope=row | ∪,∩,+,×
| [[NEXPTIME]]-complete
| [[NP-complete]]
|-
! scope=row | ∪,+,×
| [[PSPACE]]-complete
| [[NP-complete]]
|-
! scope=row | ∩,+,×
| [[P (complexity)|P]]-hard, in co-R
| [[LOGCFL]]
|-
! scope=row | +,×
| [[P (complexity)|P]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪,∩,−,+
| [[PSPACE]]-complete
| [[PSPACE]]-complete
|-
! scope=row | ∪,∩,+
| [[PSPACE]]-complete
| [[NP-complete]]
|-
! scope=row | ∪,+
| [[NP-complete]]
| [[NP-complete]]
|-
! scope=row | ∩,+
| [[CL (complexity)|C=L]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | +
| [[CL (complexity)|C=L]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪,∩,−,×
| [[PSPACE]]-complete
| [[PSPACE]]-complete
|-
! scope=row | ∪,∩,×
| [[PSPACE]]-complete
| [[NP-complete]]
|-
! scope=row | ∪,×
| [[NP-complete]]
| [[NP-complete]]
|-
! scope=row | ∩,×
| [[CL (complexity)|C=L]]-hard, in [[P (complexity)|P]]
| [[L (complexity)|L]]-complete
|-
! scope=row | ×
| [[NL (complexity)|NL]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪,∩,−
| [[P (complexity)|P]]-complete
| [[NC (complexity)|NC1]]-complete
|-
! scope=row | ∪,∩
| [[P (complexity)|P]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪
| [[NL (complexity)|NL]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∩
| [[NL (complexity)|NL]]-complete
| [[L (complexity)|L]]-complete
|}

=== 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.<ref>
{{Citation
| author = Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers and Matthias Waldherr
| title = Equivalence Problems for Circuits over Sets of Natural Numbers
| journal = Lecture Notes in Computer Science
| volume = Volume 4649/2007
| edition= (what is called "number" in bibtex)
| year = 2007
| isbn = 978-3-540-74509-9
| pages =127–138
| doi =10.1007/978-3-540-74510-5
| publisher = Springer
| place = Berlin / Heidelberg
| url = http://www.springerlink.com/content/c007kk787054v746/
}}
</ref> We call EC(O) and EF(O) the problem of equivalence over circuits and formulae the gate of which are in O.

{| class="wikitable" style="text-align:center; width:80%;"
|+ Complexity
|-
! scope=col | O
! scope=col | EC(O)
! scope=col | EF(O)
|-
! scope=row | ∪,∩,−,+,×
| [[NEXPTIME]]-hard
Decidable with an [[oracle machine|oracle]] for the [[halting problem]]
| [[PSPACE]]-hard
Decidable with an [[oracle machine|oracle]] for the [[halting problem]]
|-
! scope=row | ∪,∩,+,×
| [[NEXPTIME]]-hard, in co[[NEXPTIME|NEXP]][[NP (complexity)|NP]]
| [[Polynomial hierarchy|ΠP2]]-complete
|-
! scope=row | ∪,+,×
| [[NEXPTIME]]-hard, in co[[NEXPTIME|NEXP]][[NP (complexity)|NP]]
| [[Polynomial hierarchy|ΠP2]]-complete
|-
! scope=row | ∩,+,×
| [[P (complexity)|P]]-hard, in [[Bounded-error probabilistic polynomial|BPP]]
| [[L (complexity)|L]]-hard, in [[LOGCFL]]
|-
! scope=row | +,×
| [[L (complexity)|L]]-hard, in [[LOGCFL]]
| [[P (complexity)|P]]-hard, in co[[RP (complexity)|RP]]
|-
! scope=row | ∪,∩,−,+
| [[PSPACE]]-complete
| [[PSPACE]]-complete
|-
! scope=row | ∪,∩,+
| [[PSPACE]]-complete
| [[Polynomial hierarchy|ΠP2]]-complete
|-
! scope=row | ∪,+
| [[Polynomial hierarchy|ΠP2]]-complete
| [[Polynomial hierarchy|ΠP2]]-complete
|-
! scope=row | ∩,+
| co[[CL (complexity)|C=L]](2)-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | +
| [[CL (complexity)|C=L]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪,∩,−,×
| [[PSPACE]]-complete
| [[PSPACE]]-complete
|-
! scope=row | ∪,∩,×
| [[PSPACE]]-complete
| [[Polynomial hierarchy|ΠP2]]-complete
|-
! scope=row | ∪,×
| [[Polynomial hierarchy|ΠP2]]-complete
| [[Polynomial hierarchy|ΠP2]]-complete
|-
! scope=row | ∩,×
| co[[CL (complexity)|C=L]](2)-hard, in [[P (complexity)|P]]
| [[L (complexity)|L]]-complete
|-
! scope=row | ×
| [[CL (complexity)|C=L]]-hared, in [[P (complexity)|P]]
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪,∩,−
| [[P (complexity)|P]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪,∩
| [[P (complexity)|P]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∪
| [[NL (complexity)|NL]]-complete
| [[L (complexity)|L]]-complete
|-
! scope=row | ∩
| [[NL (complexity)|NL]]-complete
| [[L (complexity)|L]]-complete
|}

== References ==
{{Reflist}}
*{{Citation
| last = Travers
| first =Stephen
| year =2006
| title =The Complexity of Membership Problems for Circuits over Sets of Natural Numbers
| publisher=Theoretical Computer Science
| volume =389
| issue =1
| pages =211–229
| url =http://portal.acm.org/citation.cfm?id=1238761
| issn =0304-3975
| ref=travers
}}

*{{Citation
| author = Pierre McKenzie and Klaus W. Wagner
| title = The Complexity of Membership Problems for Circuits over Sets of Natural Numbers
| journal = Lecture Notes In Computer Science
| volume = 2607
| year = 2003
| isbn =3-540-00623-0
| pages =571–582
| publisher = Springer-Verlag
| url = http://portal.acm.org/citation.cfm?id=646517.696311
}}

== External links ==
* Pierre McKenzie, [http://www.iro.umontreal.ca/~mckenzie/Dagstuhl02.pdf The complexity of circuit evaluation over the natural numbers]

[[Category:Computational complexity theory]]
[[Category:Arithmetic]]

formulasearchengine - User contributions [en]

Orlicz–Pettis theorem