J'ai vu comment XOR-3-SAT est efficacement résoluble (par exemple, voir la section "XOR-satisfiabilité" dans l'entrée Wikipedia pour le problème de satisfiabilité booléenne ).
Je me pose une question de base: XOR-k-SAT est-il efficacement résoluble, pour des formules avec des quantités variables de littéraux par clause?
J'aimerais vraiment savoir si nous pouvons augmenter le nombre de littéraux par article au-delà de 3 et si nous pouvons avoir des longueurs mixtes.
complexity-theory
satisfiability
Matt Groff
la source
la source
Réponses:
Il semble que l'article Wikipédia auquel vous avez lié indique que XORSAT (pas seulement 3-XORSAT) est en P. La méthode par laquelle ils résolvent cette formule 3-XORSAT dans leur exemple se généralise très facilement aux formules dans lesquelles les clauses peuvent avoir arbitrairement un grand nombre de variables et un nombre différent de variables.
Vous regardez simplement la formule comme un système d'équations linéaires où vous avez une équation pour chaque clause et une variable pour chaque variable. Par exemple, la formule:
a une affectation satisfaisante si et seulement si le système d'équations suivant a une solution:
Et nous pouvons trouver des solutions à des systèmes linéaires d'équations comme celles-ci en temps polynomial en utilisant l'élimination gaussienne!
la source
Oui. Il est résoluble par élimination gaussienne. L'élimination gaussienne peut résoudre tout système d'équations modulo linéaire. XOR agit comme un module d'addition 2, donc chaque clause XOR-SAT agit comme un modulo d'équation linéaire 2. Par conséquent, l'élimination gaussienne peut résoudre n'importe quelle formule XOR-k-SAT ou toute formule XOR-SAT, même s'il existe un nombre variable de littéraux par clause ou longueurs de clause mixtes, en temps polynomial.
la source