Formal definition
A natural number circuit is a circuit, i.e. a labelledAlgorithmic problems
One can ask: *Is a given number ''n'' a member of the output node. *Is the output node empty? *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 .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 aQuickly 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 , then one can easily prove by induction on that , indeed and by induction . And even double exponential—sized sets: let , then , i.e. contains the firsts number. Once again this can be proved by induction on , it is true for by definition and let , dividing by we see that it can be written as where , and by induction, and are in , so indeed . 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.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. We call EC(O) and EF(O) the problem of equivalence over circuits and formulae the gates of which are in O.References
* * *{{Citation , last =Breunig , first =Hans-Georg , title = The complexity of membership problems for circuits over sets of positive numbers , volume = FCT'07 Proceedings of the 16th international conference on Fundamentals of Computation Theory , pages =125–136 , year = 2007 , isbn =978-3-540-74239-5 , publisher =Springer-Verlag , url = https://portal.acm.org/citation.cfm?id=2391509External links
* Pierre McKenzie