Combien de clauses sont nécessaires pour SAT pour être np-dur dans les formules CNF?

Question

Il n'est pas difficile de voir que SAT pour une formule CNF avec $ n $ variables et un nombre constant de clauses peuvent être résolus en temps polynomial. D'autre part, il n'est pas difficile de voir qu'une formule CNF avec $ n $ variables et $ o (n) $ Les clauses suffisent pour la dureté NP (considérez par exemple les instances de SAT associées à la formule naturelle pour 3 colorabilité, appliquées aux graphiques planaires).

Nous pourrions définir cela formellement comme $ \ texte {cnfsat} -f- \ texte {clauses} $ , une famille de problèmes paramétrés par une fonction $ F $ , dans quels instances sont formules dans CNF de telle sorte que si elles ont $ n $ variables, puis ils ont à la plupart $ f (n) $ clauses. Basé sur cela, ce que j'aimerais savoir, c'est quelle est la plus petite fonction $ g $ telle que nous savons qu'il existe $ f \ in o (g) $ tel que $ \ texte {cnfsat} -f- \ texte {clauses} $ est déjà np-dur. Nous savons que g= 1 (nombre constant de clauses) ne fonctionne pas et $ g= n $ (nombre linéaire de clauses) fonctionne.

Qu'en est-il de $ g=journal n $ ? Existe-t-il un simple algorithme pour CNFSAT sur des formules $ O (\ LG \ LG N) $ clauses?

Answer 1

limite inférieure. pour $ g \ le c \ cdot \ sqrt {\ journal n} $ il existe un algorithme de temps polynomial . L'idée est la suivante: Si certaines clauses ont trop de variables, il devrait être trivial de sélectionner une variable pour satisfaire cette clause, sans blesser des clauses avec peu de variables. Nous répétons ce qui suit:

Recherchez la clause avec le plus petit nombre de variables. Laissez $ x_1, \ ldots, x_k $ être les variables participant à cette clause.

• si $ k> g $ , la formule totale est satisfaite (nous traitons des clauses une par une et sélectionnez une variable que nous n'avons pas sélectionnée auparavant).
• Sinon, nous supprimons la clause. Nous supprimons également $ x_1, \ ldots, x_k $ de toutes les autres clauses.

Maintenant, nous devons satisfaire les clauses supprimées. Comme il y a au plus $ g $ clauses et chacun d'entre eux introduit au plus $ g $ nouvelles variables, Cela signifie qu'il y a au plus $ g ^ 2= c ^ 2 \ cdot \ journal n $ variables globales. Par conséquent, il y en a au plus $ n ^ {c ^ 2} $ combinaisons variables, et nous pouvons simplement utiliser la force brute.

limite supérieure conditionnelle. c'est presque serré dans le sens suivant. suppose que la liaison inférieure sur le SAT avec $ n $ variables et $ \ ge c \ CDOT N $ clauses (pour certains $ C $ , par exemple venant de $ 3 $ -coloring ) Est $ \ ALPHA ^ N $ ( $ \ alpha \ in (1, 2] $ ). Notez que la même liaison inférieure détient après notre transformation (puisque nous pouvons simplement l'appliquer avant tout algorithme). Par conséquent, s'il y a au moins $ \ {1+ \ epsilon} n $ clauses, ils peuvent avoir $ \ frac {\ log ^ {1+ \ epsilon} n} C $ variables et la limite inférieure de l'heure de fonctionnement pour Notre problème est

$$ \ alpha ^ {\ frac {\ journal ^ {1+ \ epsilon} n} c}= n ^ {\ frac {\ log ^ \ epsilon n \ CDOT \ journal \ alpha} {c}}, $$

qui est super polynomial.