Los circuitos sobre números naturales son un modelo matemático utilizado en el estudio de la teoría de la complejidad computacional . Son un caso especial de circuitos . El objeto es un gráfico acíclico dirigido etiquetadocuyos nodos evalúan a 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 es encontrar 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.
Definicion formal
Un circuito de números naturales es un circuito , es decir, un gráfico acíclico dirigido etiquetado de grado interno como máximo 2. Los nodos de grado interno 0, las hojas, son conjuntos finitos de números naturales, las etiquetas de los nodos de grado interno 1 son -, donde y las etiquetas de los nodos de grado 2 son +, ×, ∪ y ∩, donde , y ∪ y ∩ con el significado de conjunto habitual .
También se estudia el subconjunto de circuitos que no utilizan todas las etiquetas posibles.
Problemas algorítmicos
Uno puede preguntar:
- Es un número dado n miembro del nodo de salida.
- ¿Está vacío el nodo de salida?
- Es un nodo es un subconjunto de otro.
Para los circuitos que utilizan todas las etiquetas, todos estos problemas son equivalentes.
Prueba
El primer problema se puede reducir al segundo, tomando la intersección de la puerta de salida y n . De hecho, el nuevo get de salida estará vacío 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 se puede reducir al primero, basta con multiplicar la puerta de salida por 0, entonces 0 estará en la puerta de salida si y solo si la puerta de salida anterior no estuviera vacía.
El tercer problema se puede reducir al segundo, comprobar si A es un subconjunto de B es equivalente a preguntar si hay un elemento en .
Restricciones
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) el mismo problema con la restricción añadida de que el circuito debe ser un árbol .
Conjunto de rápido crecimiento
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 . Dejar, entonces uno puede probar fácilmente por inducción en que , Por supuesto y por inducción .
E incluso conjuntos de tamaño doble exponencial: deje , luego , es decir contiene la primer número. Una vez más, esto se puede probar por inducción en, es cierto para por definición y dejar , dividiendo por vemos que se puede escribir como dónde , y por inducción, y estan en , así que de hecho .
Estos ejemplos explican por qué la suma y la multiplicación son suficientes para crear problemas de alta complejidad.
Resultados de complejidad
Problema de membresía
El problema de membresía 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 la pertenencia se encuentra dentro de clases de complejidad bien conocidas. Tenga en cuenta que la variable de tamaño aquí es el tamaño del circuito o árbol; se supone que el valor de n es fijo.
O | MC (O) | MF (O) |
---|---|---|
∪, ∩, -, +, × | NEXPTIME -duro Decidible con un oráculo para el problema de la detención | PSPACE -duro |
∪, ∩, +, × | NEXPTIME -completo | NP-completo |
∪, +, × | PSPACE -completo | NP-completo |
∩, +, × | P -duro, en co- RP | en D LOGCFL |
+, × | P -completo | en D LOGCFL |
∪, ∩, -, + | PSPACE -completo | PSPACE -completo |
∪, ∩, + | PSPACE -completo | NP-completo |
∪, + | NP-completo | NP-completo |
∩, + | C = L -completo | en L |
+ | C = L -completo | en L |
∪, ∩, -, × | PSPACE -completo | PSPACE -completo |
∪, ∩, × | PSPACE -completo | NP-completo |
∪, × | NP-completo | NP-completo |
∩, × | C = L -duro, en P | en L |
× | NL -completo | en L |
∪, ∩, - | P -completo | NC 1 -completo |
∪, ∩ | P -completo | en NC 1 |
∪ | NL -completo | en NC 1 |
∩ | NL -completo | en NC 1 |
Problema de equivalencia
El problema de equivalencia pregunta si, dadas dos puertas de un circuito, 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 entre circuitos y fórmulas cuyas puertas están en O.
O | EC (O) | EF (O) |
---|---|---|
∪, ∩, -, +, × | NEXPTIME -duro Decidible con un oráculo para el problema de la detención | PSPACE -duro Decidible con un oráculo para el problema de la detención |
∪, ∩, +, × | NEXPTIME -duro, en co NEXP NP | Π P 2 -completo |
∪, +, × | NEXPTIME -duro, en co NEXP NP | Π P 2 -completo |
∩, +, × | P -duro, en BPP | P -duro, en BPP |
+, × | P -duro, en BPP | P -duro, en co RP |
∪, ∩, -, + | PSPACE -completo | PSPACE -completo |
∪, ∩, + | PSPACE -completo | Π P 2 -completo |
∪, + | Π P 2 -completo | Π P 2 -completo |
∩, + | co C = L (2) -completo | en L |
+ | C = L -completo | en L |
∪, ∩, -, × | PSPACE -completo | PSPACE -completo |
∪, ∩, × | PSPACE -completo | Π P 2 -completo |
∪, × | Π P 2 -completo | Π P 2 -completo |
∩, × | co C = L (2) -duro, en P | en L |
× | C = L -duro, en P | en L |
∪, ∩, - | P -completo | NC 1 -completo |
∪, ∩ | P -completo | NC 1 -completo |
∪ | NL -completo | en NC 1 |
∩ | NL -completo | en NC 1 |
Referencias
- ^ Christian Glaßer; Katrin Herr; Christian Reitwießner; Stephen Travers; Matthias Waldherr (2007), "Problemas de equivalencia para circuitos sobre conjuntos de números naturales", Lecture Notes in Computer Science ((lo que se llama "número" en bibtex) ed.), Berlín / Heidelberg: Springer, Volumen 4649/2007: 127 –138, doi : 10.1007 / 978-3-540-74510-5 , ISBN 978-3-540-74509-9
|volume=
tiene texto extra ( ayuda )
- Travers, Stephen (2006), "The Complexity of Membership Problems for Circuits over Sets of Natural Numbers" , Theoretical Computer Science: The Journal of the European Association for Theoretical Computer Science , 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" , Lecture Notes in Computer Science , Springer-Verlag, 2607 : 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 , FCT'07 Actas de la decimosexta conferencia internacional sobre los fundamentos de la teoría de la computación, Springer-Verlag, págs. 125-136, ISBN 978-3-540-74239-5
enlaces externos
- Pierre McKenzie, La complejidad de la evaluación de circuitos sobre los números naturales.