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.

Suponha que há um problema em SNP caracterizado por uma fórmula da forma ${\displaystyle \exists AP(A)}$, onde ${\displaystyle A}$ é um conjunto ou uma relação e ${\displaystyle 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 ${\displaystyle P}$. A classe de todos os problemas de função é chamada de ${\displaystyle MaxSNP_{0}}$ e foi definida por Christos Papadimitriou e Mihalis Yannakakis em seu artigo de 1991, "Optimization, approximation, and complexity classes."^[1]

Papadimitriou e Yannakakis continuam para completar esta classe definindo ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle MaxSNP}$; isto é, o fechamento de ${\displaystyle MaxSNP}$ sob as reduções PTAS é APX.

• 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 

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