Pourquoi ne pas faire ces vérifications sur le nombre de clauses en 3-SAT?
-
05-11-2019 - |
Question
J'ai écrit un solveur à 3 pour le plaisir et en comparant ses performances avec le solveur pycosat. Mon solveur surpasse largement Pycosat dans deux cas spéciaux, où je résolve en faisant des vérifications simples et évidentes, ce que Pycosat ne semble pas faire (en fonction du temps nécessaire pour résoudre ces cas).
J'ai présumé que ces chèques seraient connus et généralement incorporés dans les solveurs. Est-ce le cas? Pourquoi un solveur ne prendrait-il pas la peine de les faire?
Les chèques sont basés sur ce qui suit:
Laisser $ phi $ être un CNF avec $ n $ variables et $ m $ disjonctions, où chaque disjonction a exactement 3 variables distinctes et pas deux disjonctions n'ont les mêmes littéraux.
1) Si $ m <8 $, alors $ phi $ est satisfait.
2) Si $ m> 7 * binom {n} {3} $, alors $ phi $ n'est insatisfaisable. ($ binom {n} {k} $ est le coefficient binomial.)
La preuve est simple mais fastidieuse. Je peux le fournir si nécessaire.
Pas de solution correcte