Complexité de cas spécifiques de max2sat

Question

Je sais que Max2sat est NP-complet en général mais je me demande si certains cas restreints sont connus pour être dans P. Certainement les langues

$ l_k:={\ phi \, | \, \ phi \, \ text {est une instance de 2SAT qui a une affectation satisfaisant au moins k clauses.} \ } $

peut être résolu dans $ O (n ^ k) $ via la recherche de force brute depuis pour chaque langue $ k $ est corrigé. Cependant, je me demande sur le cas lorsqu'une fraction des clauses est spécifiée. Est-ce que toute fraction donnait un problème de NP-dur? Spécifiquement, je me demande sur le cas de satisfaire au moins la moitié des clauses d'une instance 2SAT.

La réduction que j'ai vue de 3SAT à MAX2SAT construit 10 clauses de chaque clause de 3SAT de telle sorte que sur ces dix, exactement 7 sont satisfaites lorsque la clause de 3sat originale est satisfaite et au plus 6 sont satisfaites lorsque la clause d'origine n'est pas satisfaite. . Donc dans cette réduction, la fraction de 7/10 $ fonctionne mais 1/2 $ n'est pas parce que la vérité insatisfaisante Les affectations d'une instance 3SAT peuvent toujours donner une instance de 2SAT qui a une cession satisfaisant plus de la moitié des clauses. J'ai pensé à une autre construction ou en ajoutant des clauses supplémentaires à une instance de 2SAT, mais j'ai échoué jusqu'à présent.

Answer 1

Vous pouvez toujours satisfaire au moins la moitié des clauses: pour chaque variable $ x $ , trouve le nombre de clauses contenant $ x $ et le nombre de clauses contenant $ \ lnot x $ . Sélectionnez celui qui satisfait au plus de clauses. Retirez les clauses contenant $ x $ et $ \ lnot x $ . Répéter pour d'autres variables.

depuis pour chaque $ x $ Nous satisfonons au moins la moitié des clauses supprimées, nous satisfonons la moitié des clauses globales.

D'autre part, il est aussi serré: laisser $ \ alpha> \ frac 12 $ soit la fraction des clauses pour lesquelles nous pouvons donner une réponse. Laissez $ \ beta> \ frac 12 $ est la fraction maximale des clauses que nous pouvons satisfaire dans une clause spécifique. Ensuite, nous pouvons ajouter des clauses afin que $ \ beta $ (pour la nouvelle clause) devient une clause arbitraire à $ \ alpha $ < / span>:

• si $ \ beta <\ alpha $ , nous pouvons ajouter des clauses $ (x_i \ lor \ lnot x_i) $ , jusqu'à $ \ beta> \ alpha $ (puisque ces clauses sont toujours vraies, $ \ beta $ augmente).
• si $ \ beta> \ alpha $ , nous pouvons ajouter des clauses $ (x_i) $ et $ (\ lnot x_i) $ , jusqu'à $ \ beta <\ alpha $ (depuis exactement la moitié des clauses est vrai, $ \ beta $ diminue).

Je n'ai pas choisi, mais pour obtenir $ o (\ frac 1m) $ différence (c'est-à-dire pour trouver le nombre exact de clauses), je pense qu'il suffit de suffire ajouter $ o (m) $ clauses. En d'autres termes, si nous pouvons résoudre certains $ \ alpha> \ frac 12 $ , nous pouvons vérifier n'importe quel $ \ BETA $ si $ \ beta $ fraction des clauses peut être satisfaite et nous pouvons donc résoudre max2sat en temps polynomial.