1 Answers
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.
4 views
Answered