Complexidade de casos específicos de max2sat

Question

Eu sei que o Max2Sat é NP-completo em geral, mas estou me perguntando se certos casos restritos são conhecidos por estarem em p. Certamente os idiomas

$ l_k:= {\ phi \, | \, \ phi \, \ text {é uma instância de 2SAT que tem uma tarefa satisfazendo pelo menos k cláusulas.} } $

Pode ser resolvido em $ o (n ^ k) $ através da pesquisa de força bruta desde cada linguagem $ k $ é corrigido. No entanto, estou me perguntando sobre o caso quando uma fração das cláusulas é especificada. Alguma fração produz um problema NP-Hard? Especificamente, estou me perguntando sobre o caso de satisfazer pelo menos metade das cláusulas de uma instância de 2 segundos.

A redução que vi de 3sat para o Max2Sat constrói 10 cláusulas de cada cláusula em 3sat tal que fora desses dez, exatamente 7 são satisfeitos quando a cláusula 3SAT original é satisfeita e no máximo 6 são satisfeitas quando a cláusula original não está satisfeita quando a cláusula original não está satisfeita . Então, nesta redução a fração de $ 7/10 $ funciona, mas $ 1/2 $ não porque a verdade insatisfatória As atribuições de uma instância de 3 receber ainda podem produzir uma instância de 2sat que tenha uma tarefa que satisfaça mais da metade das cláusulas. Eu pensei em outra construção ou adicionando cláusulas extras a uma instância de 2,sat, mas eu não tenho sucesso até agora.

Answer 1

Você sempre pode satisfazer pelo menos metade das cláusulas: Para cada variável $ x $ , encontre o número de cláusulas que contêm $ x $ e o número de cláusulas que contêm $ \ lnot x $ . Selecione o que satisfaça mais cláusulas. Remover cláusulas contendo $ x $ e $ \ lnot x $ . Repita para outras variáveis.

Desde um $ x $ satisfazemos pelo menos metade das cláusulas removidas, satisfazemos metade das cláusulas em geral.

Por outro lado, também é apertado: Deixe $ \ alfa> \ FRAC 12 $ ser a fração de cláusulas para as quais podemos dar uma resposta. Deixe $ \ beta> \ FRAC 12 $ Seja a fração máxima de cláusulas que podemos satisfazer em uma cláusula específica. Em seguida, podemos adicionar cláusulas para que $ \ beta $ (para a nova cláusula) torna-se cláusula arbitrária para $ \ alfa $ < / SPAN>:

• se $ \ beta <\ alpha $ , então podemos adicionar clauses $ (x_i \ lor \ lnot x_i) $ , até $ \ beta> \ alfa $ (já que essas cláusulas são sempre verdadeiras, $ \ beta $ aumentos).
• se $ \ beta> \ alfa $ , podemos adicionar clauses $ (x_i) $ e $ (\ lnot x_i) $ , até $ \ beta <\ alpha $ (já que exatamente metade das cláusulas é verdade, $ \ beta $ diminui).

Eu não verifiquei, mas para obter $ O (\ Frac 1m) $ diferença (isto é, para encontrar o número exato de cláusulas), eu acho que é suficiente Para adicionar $ o (m) $ cláusulas. Em outras palavras, se pudermos resolver para alguma $ \ alfa> \ FRAC 12 $ , podemos verificar se há qualquer $ \ beta $ se $ \ beta $ fração de cláusulas pode ser satisfeito e, portanto, podemos resolver o Max2Sat no tempo polinomial.