SNP (complejidad)

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 de la teoría 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 los grafos ) expresables mediante una fórmula lógica de segundo orden de la siguiente forma:

${\displaystyle \exists S_{1}\dots \exists S_{\ell }\,\forall v_{1}\dots \forall v_{m}\,\phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})}$

dónde${\displaystyle R_{1},\dots ,R_{k}}$son relaciones de la estructura (como la relación de adyacencia, para un grafo),${\displaystyle S_{1},\dots ,S_{\ell }}$son relaciones desconocidas (conjuntos de tuplas de vértices), y${\displaystyle \phi }$es una fórmula sin 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 estructuras relacionales que están en NP), un hecho conocido como el teorema de Fagin .

Por ejemplo, SNP contiene el problema de la 3-coloración (el problema de determinar si un grafo dado es 3-coloreable ), porque se puede expresar mediante la siguiente fórmula:

${\displaystyle \exists S_{1}\exists S_{2}\exists S_{3}\,\forall u\forall v\,{\bigl (}S_{1}(u)\vee S_{2}(u)\vee S_{3}(u){\bigr )}\,\wedge \,{\bigl (}E(u,v)\,\implies \,(\neg S_{1}(u)\vee \neg S_{1}(v))\,\wedge \,\left(\neg S_{2}(u)\vee \neg S_{2}(v)\right)\,\wedge \,(\neg S_{3}(u)\vee \neg S_{3}(v)){\bigr )}}$

Aquí${\displaystyle E}$denota la relación de adyacencia del grafo de entrada, mientras que los conjuntos (relaciones unarias)${\displaystyle S_{1},S_{2},S_{3}}$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 como máximo 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 satisfaga para todas las tuplas, se busca maximizar el número de tuplas para las que se satisface. Es decir, MaxSNP ₀ se define como la clase de problemas de optimización en estructuras relacionales que se pueden expresar de la siguiente forma:

${\displaystyle \max \limits _{S_{1},\dots ,S_{\ell }}|\{(v_{1},\dots ,v_{m})\colon \phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})\}|}$

MaxSNP se define entonces como la clase de todos los problemas con una L-reducción ( reducción lineal , no reducción de espacio logarítmico ) a problemas en MaxSNP ₀ . ^{[ 2 ]} Por ejemplo, MAX-3SAT es un problema en MaxSNP ₀ : 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), encontrar 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 generales que las reducciones L) es igual a APX ; es decir, todo problema en APX tiene una reducción PTAS a él desde algún problema en MaxSNP . En particular, todo problema MaxSNP -completo (bajo reducciones L o bajo reducciones AP ) es también APX -completo (bajo reducciones PTAS), y por lo tanto no admite un PTAS a menos que P=NP . Sin embargo, la demostración de esto se basa en el teorema PCP , mientras que las demostraciones de la completitud de MaxSNP suelen ser elementales.

• APX

• 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 Ciencias de la Computación Teórica. Una serie de EATCS. ​​Berlín: Springer-Verlag . pág. 350. ISBN  978-3-540-00428-8. Zbl 1133.03001 . 

• Zoológico de la complejidad : SNP
• Complexity Zoo : MaxSNP
• Zoológico de complejidad : MaxSNP ₀