Circuits over sets of natural numbers

Last updated December 20, 2023

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.

Formal definition

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

One can ask:

Is a given number n a member of the output node.
Is the output node empty?
Is one node 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 $A\cap {\overline {B}}$ .

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.

Quickly growing set

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}\times 2}\}=\{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

Membership problem

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. Note that the size variable here is the size of the circuit or tree; the value of n is assumed to be fixed.

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-RP	in DLOGCFL
+,×	P-complete	in DLOGCFL
∪,∩,−,+	PSPACE-complete	PSPACE-complete
∪,∩,+	PSPACE-complete	NP-complete
∪,+	NP-complete	NP-complete
∩,+	C₌L-complete	in L
+	C₌L-complete	in L
∪,∩,−,×	PSPACE-complete	PSPACE-complete
∪,∩,×	PSPACE-complete	NP-complete
∪,×	NP-complete	NP-complete
∩,×	C₌L-hard, in P	in L
×	NL-complete	in L
∪,∩,−	P-complete	NC¹-complete
∪,∩	P-complete	in NC¹
∪	NL-complete	in NC¹
∩	NL-complete	in NC¹

Equivalence problem

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 coNEXP ^NP	Π^P₂-complete
∪,+,×	NEXPTIME-hard, in coNEXP ^NP	Π^P₂-complete
∩,+,×	P-hard, in BPP	P-hard, in BPP
+,×	P-hard, in BPP	P-hard, in coRP
∪,∩,−,+	PSPACE-complete	PSPACE-complete
∪,∩,+	PSPACE-complete	Π^P₂-complete
∪,+	Π^P₂-complete	Π^P₂-complete
∩,+	coC₌L(2)-complete	in L
+	C₌L-complete	in L
∪,∩,−,×	PSPACE-complete	PSPACE-complete
∪,∩,×	PSPACE-complete	Π^P₂-complete
∪,×	Π^P₂-complete	Π^P₂-complete
∩,×	coC₌L(2)-hard, in P	in L
×	C₌L-hard, in P	in L
∪,∩,−	P-complete	NC¹-complete
∪,∩	P-complete	NC¹-complete
∪	NL-complete	in NC¹
∩	NL-complete	in NC¹

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers or the computable reals or recursive reals. The concept of a computable real number was introduced by Emile Borel in 1912, using the intuitive notion of computability available at the time.

In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time $O ((log n) c)$ using $O (n k)$ parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of

In mathematics, the transitive closure $R +$ of a homogeneous binary relation $R$ on a set $X$ is the smallest relation on $X$ that contains $R$ and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets $R +$ is the unique minimal transitive superset of $R$ .

In Vapnik–Chervonenkis theory, the Vapnik–Chervonenkis (VC) dimension is a measure of the size of a class of sets. The notion can be extended to classes of binary functions. It is defined as the cardinality of the largest set of points that the algorithm can shatter, which means the algorithm can always learn a perfect classifier for any labeling of at least one configuration of those data points. It was originally defined by Vladimir Vapnik and Alexey Chervonenkis.

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

In computational complexity theory, P, also known as PTIME or DTIME(n^O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology. This space is commonly used in descriptive set theory, to the extent that its elements are often called "reals". It is denoted N^N, ^ωω, by the symbol $or also ω ω, not to be confused with the countable ordinal obtained by ordinal exponentiation.$

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with " $" and " " of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.$

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits $.$

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897. The Dedekind number M(n) is the number of monotone boolean functions of n variables. Equivalently, it is the number of antichains of subsets of an n-element set, the number of elements in a free distributive lattice with n generators, and one more than the number of abstract simplicial complexes on a set with n elements.

In computational complexity theory, arithmetic circuits are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expressions it has already computed. Arithmetic circuits provide a formal way to understand the complexity of computing polynomials. The basic type of question in this line of research is "what is the most efficient way to compute a given polynomial $?"$

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical model for digital logic circuits. Circuits are defined by the gates they contain and the values the gates can produce. For example, the values in a Boolean circuit are boolean values, and the circuit includes conjunction, disjunction, and negation gates. The values in an integer circuit are sets of integers and the gates compute set union, set intersection, and set complement, as well as the arithmetic operations addition and multiplication.

In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true. By a result in descriptive complexity, a set of natural numbers is a spectrum if and only if it can be recognized in non-deterministic exponential time.

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

References

↑ Christian Glaßer; Katrin Herr; Christian Reitwießner; Stephen Travers; Matthias Waldherr (2007), Computer Science – Theory and Applications, Lecture Notes in Computer Science, vol. 4649/2007 ((what is called "number" in bibtex) ed.), Berlin / Heidelberg: Springer, pp. 127–138, doi:10.1007/978-3-540-74510-5, ISBN 978-3-540-74509-9

Travers, Stephen (2006), "The Complexity of Membership Problems for Circuits over Sets of Natural Numbers", Theoretical Computer Science, 389 (1): 211–229, doi: 10.1016/j.tcs.2006.08.017 , ISSN 0304-3975

Pierre McKenzie; Klaus W. Wagner (2003), "The Complexity of Membership Problems for Circuits over Sets of Natural Numbers", Stacs 2003, Lecture Notes in Computer Science, vol. 2607, Springer-Verlag, pp. 571–582, doi:10.1007/3-540-36494-3_50, ISBN 3-540-00623-0

Breunig, Hans-Georg (2007), The complexity of membership problems for circuits over sets of positive numbers, vol. FCT'07 Proceedings of the 16th international conference on Fundamentals of Computation Theory, Springer-Verlag, pp. 125–136, ISBN 978-3-540-74239-5

External links

Pierre McKenzie, The complexity of circuit evaluation over the natural numbers

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Christian Glaßer; Katrin Herr; Christian Reitwießner; Stephen Travers; Matthias Waldherr (2007), Computer Science – Theory and Applications, Lecture Notes in Computer Science, vol. 4649/2007 ((what is called "number" in bibtex) ed.), Berlin / Heidelberg: Springer, pp. 127–138, doi:10.1007/978-3-540-74510-5, ISBN 978-3-540-74509-9

[1]