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.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Circuits over sets of natural numbers (en)
- Circuitos sobre conjuntos de números naturais (pt)
|
rdfs:comment
| - 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. (en)
- Circuitos sobre conjuntos de números naturais são um modelo matemático utilizado no estudo da teoria da complexidade computacional. Eles são um caso especial de circuitos. O objeto é classificado como grafo acíclicos dirigidos a nós do que avaliar os conjuntos dos números naturais, as folhas são conjuntos finitos, e as portas são operações de conjuntos ou operações aritméticas. Como um problema algorítmico, o problema é descobrir se um dado número natural é um elemento do nó de saída ou se dois circuitos calculam o mesmo conjunto. Decidibilidade é ainda uma questão em aberto. (pt)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - 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. (en)
- Circuitos sobre conjuntos de números naturais são um modelo matemático utilizado no estudo da teoria da complexidade computacional. Eles são um caso especial de circuitos. O objeto é classificado como grafo acíclicos dirigidos a nós do que avaliar os conjuntos dos números naturais, as folhas são conjuntos finitos, e as portas são operações de conjuntos ou operações aritméticas. Como um problema algorítmico, o problema é descobrir se um dado número natural é um elemento do nó de saída ou se dois circuitos calculam o mesmo conjunto. Decidibilidade é ainda uma questão em aberto. (pt)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is foaf:primaryTopic
of | |