En la teoría de la complejidad computacional , SNP (de Strict NP ) es una clase de complejidad que contiene un subconjunto limitado de NP en función de su caracterización lógica en términos de propiedades de teoría de grafos . Forma la base para la definición de la clase MaxSNP de los problemas de optimización .
Se define como la clase de problemas que son propiedades de estructuras relacionales (como los grafos ) expresables mediante una fórmula lógica de segundo orden de la siguiente forma:
donde son relaciones de la estructura (como la relación de adyacencia, para un grafo), 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, solo se permite la cuantificación existencial de segundo orden (sobre relaciones) y solo 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 las estructuras relacionales que están en NP), un hecho conocido como el teorema de Fagin .
Por ejemplo, SNP contiene 3-coloración (el problema de determinar si un gráfico dado es 3-coloreable ), porque puede expresarse mediante la siguiente fórmula:
Aquí se denota la relación de adyacencia del grafo 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 a un máximo de k literales por cláusula, donde k es fijo.
Una definición análoga considera los problemas de optimización , cuando en lugar de pedir que una fórmula se cumpla para todas las tuplas, se desea maximizar el número de tuplas para las que se cumple. Es decir, MaxSNP 0 se define como la clase de problemas de optimización sobre estructuras relacionales expresables en la siguiente forma:
MaxSNP se define entonces como la clase de todos los problemas con una L-reducción ( reducción lineal , no reducción logarítmica ) 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 booleana con la fórmula en forma normal conjuntiva y como máximo 3 literales por cláusula), encuentre una asignación que satisfaga 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 aproximables dentro de alguna razón constante. De hecho, el cierre de MaxSNP bajo reducciones PTAS (ligeramente más general que las reducciones L) es igual a APX ; es decir, cada problema en APX tiene una reducción PTAS a partir de algún problema en MaxSNP . En particular, cada problema MaxSNP -completo (bajo reducciones L o bajo reducciones AP ) también es APX -completo (bajo reducciones PTAS), y por lo tanto no admite un PTAS a menos que P=NP . Sin embargo, la prueba de esto se basa en el teorema PCP , mientras que las pruebas de MaxSNP -completitud son a menudo elementales.
{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )