SNP (complexidade)

Na teoria da complexidade computacional, SNP (de Strict NP) é uma classe de complexidade que contém um subconjunto limitado de NP baseado em sua caracterização lógica em termos de propriedades da Teoria dos grafos. Ela forma a base para a definição da classe MaxSNP de problemas de otimização.

Uma caracterização da Classe de complexidade NP, como mostrado por Ronald Fagin em 1974 e relacionada ao Teorema de Fagin, é que é o conjunto de problemas que podem ser reduzidos a propriedades de grafos que podem ser expressas em Lógica de segunda ordem existencial. Esta lógica permite quantificação universal (∀) e existencial (∃) sobre vértices, mas apenas quantificação existencial  sobre conjuntos de vértices e relações entre os vértices. SNP retém quantificação existencial sobre conjuntos e relações, mas apenas permite quantificação universal sobre vértices.

SNP contém k-SAT, o Problema de satisfatibilidade booleana (SAT), onde a fórmula é restrita a forma normal conjuntiva e, no máximo, k literais por cláusula, onde k é fixo.

MaxSNP

Suponha que há um problema em SNP caracterizado por uma fórmula da forma $\exists AP(A)$, onde $A$ é um conjunto ou uma relação e $P$ é um predicado de segunda-ordem que pode usá-lo. Pode-se definir um problema de otimização  correspondente: encontrar relação ou conjunto que maximiza o número de tuplas ou elementos, respectivamente, que satisfazem o predicado $P$. A classe de todos os problemas de função é chamada de $MaxSNP_{0}$ e foi definida por Christos Papadimitriou e Mihalis Yannakakis em seu artigo de 1991, "Optimization, approximation, and complexity classes."

Papadimitriou e Yannakakis continuam para completar esta classe definindo $MaxSNP$ a classe de todos os problemas com uma L-redução (redução linear, não de log-redução de espaço) para problemas em $MaxSNP_{0}$, e mostrar que ela tem um problema completo natural: dada uma instância de 3CNFSAT (Problema de satisfatibilidade booleana com a fórmula na forma normal conjuntiva e, no máximo, 3 literais por cláusula), encontrar uma atribuição satisfatória com o maximo de cláusulas possível.

Há um algoritmo de aproximação de razão fixa para resolver qualquer problema em $MaxSNP$. Na verdade, para cada problema em APX, a classe de todos os problemas aproximáveis sob uma razão constante, há uma Redução PTAS para ele de algum problema em $MaxSNP$; isto é, o fechamento de $MaxSNP$ sob as reduções PTAS é APX.

Referências

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Col: Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 350. ISBN 978-3-540-00428-8. Zbl 1133.03001 

Ligações externas

• Zoológico de complexidades: SNP
• Zoológico de complexidades: MaxSNP
• Zoológico de complexidades: MaxSNP₀