Mínimo Verdadeiro Monótono 3SAT

11

Estou interessado em uma variação de SAT em que a fórmula CNF é monótona (nenhuma variável é negada). Essa fórmula é obviamente satisfatória.

Mas digamos que o número de variáveis ​​verdadeiras seja uma medida de quão boa é a nossa solução. Portanto, temos o seguinte problema:

MONOTONE VERDADEIRO MÍNIMO 3SAT

INSTANCE: Define U de variáveis, coleção C de cláusulas disjuntivas de 3 literais, onde um literal é uma variável (não negada).
SOLUÇÃO: Uma atribuição de verdade para U que satisfaça C.
MEDIDA: O número de variáveis ​​verdadeiras.

Alguém poderia me dar algumas observações úteis sobre esse problema?

krumpelstiltskin
fonte

Respostas:

21

Este problema é o mesmo que o problema Vertex tampa para Hipergrafos -uniform: dado um conjunto H de subconjuntos de V de tamanho 3 cada, encontrar um subconjunto mínimo L V que intersecta a cada conjunto em H .3HV3UVH

É, portanto, NP-difícil, mas parâmetro fixo tratável. Também é NP-difícil aproximar-se de um fator de para cada ϵ > 0 . Isso foi mostrado no seguinte artigo:2ϵϵ>0

Irit Dinur, Venkatesan Guruswami, Subhash Khot e Oded Regev. Um novo PCP multicamada e a dureza da capa do vértice do hipergrafo , SIAM Journal on Computing, 34 (5): 1129-1146, 2005.

Jan Johannsen
fonte
Outra palavra-chave seria "Conjunto de três batidas". Não tenho acesso ao artigo a seguir agora, mas o título parece relevante: scholar.google.co.uk/…
Radu GRIGore
O limite de aproximação é realmente . 3ϵ
Mahdi Cheraghchi /
11
@MCH: Referência?
Tsuyoshi Ito
11
Não, seu : para a cobertura do vértice do hipergrafo k- uniforme, eles mostram dureza de aproximação para dentro ( k - 1 - ϵ ) . 2ϵk(k1ϵ)
Jan Johannsen
11
oops ... @MCH: eu sou interessado em ver o resultado também. isso implicaria que o algoritmo de aproximação trivial é o melhor que podemos esperar. 3ϵ
krumpelstiltskin
7

W[1]

q

Xq

k

k

Anthony Labarre
fonte