Circuitos sobre conjuntos de números naturales

Los circuitos sobre números naturales son un modelo matemático utilizado para estudiar la teoría de la complejidad computacional . Son un caso especial de circuitos . El objeto es un grafo acíclico dirigido y etiquetado cuyos nodos evalúan conjuntos de números naturales, las hojas son conjuntos finitos y las puertas son operaciones de conjuntos u operaciones aritméticas.

Como problema algorítmico , el problema consiste en determinar si un número natural dado es un elemento del nodo de salida o si dos circuitos calculan el mismo conjunto. La decidibilidad sigue siendo una cuestión abierta.

Un circuito de números naturales es un circuito , es decir, un grafo acíclico dirigido y etiquetado de grado de entrada como máximo 2. Los nodos de grado de entrada 0, las hojas, son conjuntos finitos de números naturales, las etiquetas de los nodos de grado de entrada 1 son −, donde y las etiquetas de los nodos de grado de entrada 2 son +, ×, ∪ y ∩, donde , y ∪ y ∩ con el significado de conjunto habitual .${\displaystyle {\overline {A}}=\{x\en \mathbb {N} |x\no \en A\}}$${\displaystyle A+B=\{a+b|a\en A,b\en B\}}$${\displaystyle A\veces B=\{a\veces b|a\en A,b\en B\}}$

También se estudia el subconjunto de circuitos que no utilizan todas las etiquetas posibles.

Uno puede preguntarse:

• ¿Es un número dado n un miembro del nodo de salida?
• ¿El nodo de salida está vacío?
• ¿Un nodo es un subconjunto de otro?

Para los circuitos que utilizan todas las etiquetas, todos estos problemas son equivalentes.

El primer problema se puede reducir al segundo, tomando la intersección de la puerta de salida y n . De hecho, la nueva salida get estará vacía si y solo si n no era un elemento de la puerta de salida anterior.

El primer problema se puede reducir al tercero, preguntando si el nodo n es un subconjunto del nodo de salida.

El segundo problema es reducible al primero, basta con multiplicar la puerta de salida por 0, entonces 0 estará en la puerta de salida si y sólo si la puerta de salida anterior no estuviera vacía.

El tercer problema es reducible al segundo, comprobar si A es un subconjunto de B es equivalente a preguntar si hay un elemento en .${\displaystyle A\cap {\overline {B}}}$

Sea O un subconjunto de {∪,∩,−,+,×}, entonces llamamos MC(O) al problema de encontrar si un número natural está dentro de la puerta de salida de un circuito cuyas etiquetas de puertas están en O, y MF(O) al mismo problema con la restricción añadida de que el circuito debe ser un árbol .

Una dificultad proviene del hecho de que el complemento de un conjunto finito es infinito y una computadora tiene solo una memoria finita. Pero incluso sin complementación, se pueden crear números exponenciales dobles . Sea , entonces se puede demostrar fácilmente por inducción sobre que , de hecho y por inducción .${\displaystyle E_{0}=\{2\},E_{i+1}=E_{i}\times E_{i}}$${\estilo de visualización i}$${\displaystyle E_{i}=\{2^{2^{i}}\}}$${\displaystyle E_{0}=\{2\}=\{2^{1}\}=\{2^{2^{0}}\}}$${\displaystyle 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}}\}}$

E incluso conjuntos de tamaño exponencial doble: sea , entonces , es decir contiene el primer número. Una vez más, esto se puede demostrar por inducción en , es cierto para por definición y sea , dividiendo por vemos que se puede escribir como donde , y por inducción, y están en , por lo que de hecho .${\displaystyle S_{0}=\{0,1,2\},S_{i+1}=(S_{i}\times S_{i})+S_{i}}$${\displaystyle \{x|0<x<2^{2^{i}}\}\subset S_{i}}$${\displaystyle S_{i}}$${\displaystyle 2^{2^{i}}}$${\displaystyle i}$${\displaystyle S_{0}}$${\displaystyle x\in \{x|0<x<2^{2^{i+1}}\}}$${\displaystyle x}$${\displaystyle 2^{2^{i}}}$${\displaystyle x=2^{2^{i}}\times d+r}$${\displaystyle d,r<2^{2^{i}}}$${\displaystyle 2^{2^{i}},d}$${\displaystyle r}$${\displaystyle S_{i}}$${\displaystyle x\in (S_{i}\times S_{i})+S_{i}}$

Estos ejemplos explican por qué la suma y la multiplicación son suficientes para crear problemas de alta complejidad.

El problema de pertenencia pregunta si, dado un elemento n y un circuito, n está en la puerta de salida del circuito.

Cuando la clase de puertas autorizadas está restringida, el problema de pertenencia se encuentra dentro de clases de complejidad bien conocidas. Nótese que la variable de tamaño aquí es el tamaño del circuito o árbol; se supone que el valor de n es fijo.

El problema de equivalencia pregunta si, dadas dos puertas de un circuito, ellas evalúan el mismo conjunto.

Cuando la clase de puertas autorizadas está restringida, el problema de equivalencia se encuentra dentro de clases de complejidad bien conocidas. ^[1] Llamamos EC(O) y EF(O) al problema de equivalencia sobre circuitos y fórmulas cuyas puertas están en O.

• Travers, Stephen (2006), "La complejidad de los problemas de pertenencia para circuitos sobre conjuntos de números naturales", Theoretical Computer Science , 389 (1): 211–229, doi : 10.1016/j.tcs.2006.08.017 , ISSN  0304-3975

• Pierre McKenzie; Klaus W. Wagner (2003), "La complejidad de los problemas de pertenencia para circuitos sobre conjuntos de números naturales", Stacs 2003, Lecture Notes in Computer Science, vol. 2607, Springer-Verlag, págs. 571–582, doi :10.1007/3-540-36494-3_50, ISBN 3-540-00623-0

• Breunig, Hans-Georg (2007), La complejidad de los problemas de pertenencia para circuitos sobre conjuntos de números positivos, vol. FCT'07 Actas de la 16.ª conferencia internacional sobre fundamentos de la teoría de la computación, Springer-Verlag, págs. 125-136, ISBN 978-3-540-74239-5

• Pierre McKenzie, La complejidad de la evaluación de circuitos sobre los números naturales