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 , onde é um conjunto ou uma relação e é 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 . A classe de todos os problemas de função é chamada de 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 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 , 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 . 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 ; isto é, o fechamento de sob as reduções PTAS é APX.