Classificação de variantes de problemas de satisfação intratáveis ​​/ tratáveis

20

Recentemente, encontrei em um artigo [1] uma versão simétrica especial do SAT chamada 2/2/4-SAT . Mas existem muitas variantes completas por aí, por exemplo: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NP

Algumas outras variantes são tratáveis: - , Planar-NAE- , ...SAT SAT2SATSAT

Existem documentos de pesquisa (ou páginas da web) que classificam todas as variantes (estranhas) que provaram ser completas (ou em )?NP PSATNPP


  1. Encontrar uma solução mais curto para o x extensão da 15-Puzzle é intratávelNNN por D. Ratner e M. Warmuth (1986)
Vor
fonte
@mrm: obrigado, eu não sabia o artigo de Schaefer ( dl.acm.org/citation.cfm?doid=800133.804350 )
Vor
1
Eu removi o "post your favorite", porque este é um exemplo de livro didático do que não perguntar no Stack Exchange . (Sim, ele funciona em Ciência da Computação Teórica até certo ponto, mas esse é um caso especial devido ao público altamente atípico.)
Gilles 'SO- deixa de ser mau'

Respostas:

18

Resultados clássicos e bem conhecidos

Como mencionado por Standa Zivny na questão relacionada da CSTheory, quais problemas no SAT são fáceis? , há um resultado bem conhecido de Schaefer de 1978 (citando a resposta de Zivny):

Se o SAT for parametrizado por um conjunto de relações permitido em qualquer instância, haverá apenas 6 casos tratáveis: 2-SAT (ou seja, todas as cláusulas são binárias), Horn-SAT, Horn-SAT, dual-Horn-SAT, affine-SAT (soluções lineares) equações em GF (2)), 0-válido (relações satisfeitas pela atribuição all-0) e 1-válido (relações satisfeitas pela atribuição all-1).

Planar-3SAT significa que a versão planar do 3SAT é conhecida por ser -completa. Ver D. Lichtenstein, fórmulas planares e seus usos, 1981 . A versão não planar do 3SAT é, obviamente, o bem conhecido problema clássico clássico .N PNPNP

O 3SAT não totalmente igual ( NAE-3SAT ) é completo. No entanto, a versão planar está em como mostra Moret, o Planar NAE3SAT está em P, 1988 .PNPP

Variantes mais recentes e / ou "estranhas"

kMonotônico colorido NAE-3SAT

Aqui está uma variante mais exótica ou estranha, um problema de decisão chamado Monotone colorido NAE-3SAT :k

Dada uma expressão monótona de CNF com exatamente três variáveis ​​distintas em cada cláusula, de modo que o gráfico de restrição seja k-colorido, a expressão não é totalmente igual?G ( ϕ ) ϕϕG(ϕ)ϕ

Aqui, o gráfico de restrição correspondente é um gráfico não direcionado simples associado a seguinte forma: Cada variável de é um vértice em e dois vértices têm uma aresta entre eles se aparecerem em alguma cláusula.ϕ ϕ GG(ϕ)ϕϕG

Para o problema está em . Para , no entanto, é completo. Veja P Jain, em uma variante do Monotone NAE-3SAT e o problema de corte sem triângulo, 2010 .P k = 5 N Pk=4Pk=5NP

Variantes lineares de CNF

Embora talvez não seja exótico ou estranho, algumas variantes conhecidas, como NAE-SAT ( SAT não totalmente igual) e XSAT ( Exat SAT; exatamente um literal em cada cláusula para 1 e todos os outros literais para 0), do problema de satisfação foram investigados na configuração linear . Cláusulas de uma fórmula linear aos pares têm no máximo uma variável em comum. Curiosamente, o status de complexidade não segue o Teorema de Schaefer.

NAE-SAT e XSAT permanecem completos quando restritos a fórmulas lineares. Além disso, NAE-SAT e XSAT ainda são -completa em fórmulas contendo apenas cláusulas de comprimento pelo menos , para cada número inteiro fixo positivo . Eles são completos para fórmulas lineares monótonas (sem literais positivos). No entanto, o NAE-SAT é decidível em tempo polinomial em fórmulas lineares exatas, onde cada par de cláusulas distintas tem exatamente uma variável em comum.N P k k 3 N PNPNPkk3NP

Alguns aspectos adicionais sobre a complexidade do NAE-SAT e XSAT sob certas suposições provavelmente ainda estão em aberto. Para obter mais detalhes, consulte, por exemplo, Porschen e Schmidt, Em algumas variantes de SAT sobre fórmulas lineares, 2009 e Porschen et al., Resultados de complexidade para problemas XSAT lineares, 2010 .

Juho
fonte