En la teoría de la complejidad computacional , un circuito de números enteros es un modelo de cálculo de circuito en el que las entradas al circuito son conjuntos de números enteros y cada puerta del circuito calcula una operación de conjunto o una operación aritmética en sus conjuntos de entrada.
Como problema algorítmico , las preguntas posibles son encontrar si un número entero dado es un elemento del nodo de salida o si dos circuitos calculan el mismo conjunto. La decidibilidad sigue siendo una cuestión abierta, pero hay resultados sobre la restricción de esos circuitos. Encontrar respuestas a algunas preguntas sobre este modelo podría servir como prueba de muchas conjeturas matemáticas importantes, como la de Goldbach .
Es una extensión natural de los circuitos sobre conjuntos de números naturales cuando el conjunto considerado contiene también enteros negativos, las definiciones, que no cambian, no se repetirán en esta página. Solo se mencionarán las diferencias.
Complejidad del problema de la membresía
El problema de miembro es el problema de decidir, dado un número entero circuito C , una entrada al circuito de X , y una específica número entero n , si el número entero n se encuentra en la salida del circuito de C cuando se proporciona con la entrada X . La complejidad computacional de este problema depende del tipo de puertas permitidos en el circuito C . [1] La siguiente tabla resume la complejidad computacional del problema de pertenencia para varias clases de circuitos enteros. Aquí, MF(O) denota las clases definidas por fórmulas O, que son circuitos O con un abanico máximo 1.
O | MC(O) | MF(O) |
---|---|---|
∪, ∩, -, +, × | NEXPTIME -duro | PSPACE -duro |
∪, ∩, +, × | NEXPTIME -completo | NP-completo |
∪, +, × | NEXPTIME -completo | NP-completo |
∩, +, × | P -duro, en co-NP | L -duro, en LOGCFL |
+, × | P -duro, en co-NP | L -duro, en LOGCFL |
∪, ∩, -, + | PSPACE -completo | PSPACE -completo |
∪, ∩, + | PSPACE -completo | NP-completo |
∪, + | NP-completo | NP-completo |
∩, + | C = L -completo | L -completo |
+ | C = L -completo | L -completo |
∪, ∩, -, × | PSPACE -completo | PSPACE -completo |
∪, ∩, × | PSPACE -completo | NP-completo |
∪, × | NP-completo | NP-completo |
∩, × | ( C = LL) -duro, en P | L -completo |
× | ( NL -completoL) -completo | L -completo |
∪, ∩, - | P -completo | L -completo |
∪, ∩ | P -completo | L -completo |
∪ | NL -completo | L -completo |
∩ | NL -completo | L -completo |
Referencias
- ^ Stephen Travers (2006), "La complejidad de los problemas de pertenencia para circuitos sobre conjuntos de números enteros", Informática teórica (1-3 ed.), Essex, Reino Unido: Elsevier Science Publishers Ltd, 369 (1): 211-229, doi : 10.1016 / j.tcs.2006.08.017 , ISSN 0304-3975