En la teoría de la complejidad computacional , SNP (de Strict NP ) es una clase de complejidad que contiene un subconjunto limitado de NP basado en su caracterización lógica en términos de propiedades teóricas de grafos . Constituye la base para la definición de la clase MaxSNP de problemas de optimización .
Se define como la clase de problemas que son propiedades de estructuras relacionales (como gráficos ) que se pueden expresar mediante una fórmula lógica de segundo orden de la siguiente forma:
- ,
dónde son relaciones de la estructura (como la relación de adyacencia, para un gráfico), son relaciones desconocidas (conjuntos de tuplas de vértices), y es una fórmula libre de cuantificadores: cualquier combinación booleana de las relaciones. [1] Es decir, sólo se permite la cuantificación existencial de segundo orden (sobre relaciones) y sólo se permite la cuantificación universal de primer orden (sobre vértices). Si también se permitiera la cuantificación existencial sobre vértices, la clase de complejidad resultante sería igual a NP (más precisamente, la clase de aquellas propiedades de estructuras relacionales que están en NP), hecho conocido como teorema de Fagin .
Por ejemplo, SNP contiene 3 colores (el problema de determinar si un gráfico dado es 3 colores ), porque se puede expresar mediante la siguiente fórmula:
- .
Aquí denota la relación de adyacencia del gráfico de entrada, mientras que los conjuntos (relaciones unarias) corresponden a conjuntos de vértices coloreados con uno de los 3 colores. De manera similar, SNP contiene el problema k -SAT: el problema de satisfacibilidad booleana (SAT) donde la fórmula está restringida a la forma normal conjuntiva y como máximo a k literales por cláusula, donde k es fijo.
MaxSNP
Una definición análoga considera problemas de optimización , cuando en lugar de pedir que se satisfaga una fórmula para todas las tuplas, se quiere maximizar el número de tuplas para las que se satisface. Es decir, MaxSNP 0 se define como la clase de problemas de optimización en estructuras relacionales expresable de la siguiente forma:
Entonces, MaxSNP se define como la clase de todos los problemas con una reducción L ( reducción lineal , no reducción del espacio logarítmico ) a problemas en MaxSNP 0 . [2] Por ejemplo, MAX-3SAT es un problema en MaxSNP 0 : dada una instancia de 3-CNF-SAT (el problema de satisfacibilidad booleano con la fórmula en forma normal conjuntiva y como máximo 3 literales por cláusula), encuentre una asignación satisfactoria tantas cláusulas como sea posible. De hecho, es un problema completo natural para MaxSNP .
Existe un algoritmo de aproximación de razón fija para resolver cualquier problema en MaxSNP , por lo tanto, MaxSNP está contenido en APX , la clase de todos los problemas que se puede aproximar dentro de una razón constante. De hecho, el cierre de MaxSNP bajo reducciones de PTAS (un poco más general que las reducciones L) es igual a APX ; es decir, cada problema en APX tiene una reducción de PTAS debido a algún problema en MaxSNP . En particular, cada problema de MaxSNP -completo (bajo L-reducciones o bajo AP-reducciones ) también es APX -completo (bajo PTAS reducciones), y por lo tanto no admite un PTAS a menos que P = NP . Sin embargo, la prueba de esto se basa en el teorema de PCP , mientras que las pruebas de la completitud de MaxSNP son a menudo elementales.
Ver también
Referencias
- ^ Feder, Tomás; Vardi, Moshe Y. (1993). "SNP monádico monótono y satisfacción de la restricción". Actas del vigésimo quinto simposio anual ACM sobre teoría de la computación . doi : 10.1145 / 167088.167245 .
- ^ Papadimitriou, Christos H .; Yannakakis, Mihalis (1991). "Clases de optimización, aproximación y complejidad". J. Comput. Syst. Sci . 43 (3): 425–440. Zbl 0765.68036 .
- Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos en Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . pag. 350 . ISBN 978-3-540-00428-8. Zbl 1133.03001 .