Considérez le problème suivant: étant donné une formule CNF et une affectation qui satisfait cette formule, y a-t-il une autre affectation satisfaisante pour cette formule? Quelle est la complexité de ce problème? (C'est sûrement en NP, mais est-il aussi difficile en NP?) Que se passe-t-il si vous...
Je veux faire un premier solveur SAT. Je connais le concours SAT et la conférence SAT, et il y a tellement de papiers sur ce sujet. Je suis un démarreur, un démarreur débordé. Par où dois-je commencer? Finalement, je veux pousser l'état de l'art. Je veux des conseils d'experts sur la façon de...
Que sait-on de la complexité de trouver des circuits minimaux qui calculent SAT jusqu'à la longueur ? nnn Plus formellement: quelle est la complexité d'une fonction qui, étant donnée en entrée, sort un circuit minimal C tel que pour toute formule φ avec | φ | ≤ n , C ( φ ) = S A T ( φ )...
Je ne comprends pas très bien pourquoi presque tous les solveurs SAT utilisent CNF au lieu de DNF. Il me semble que résoudre SAT est plus facile en utilisant DNF. Après tout, il vous suffit de parcourir l'ensemble des implicants et de vérifier si l'un d'eux ne contient pas à la fois une variable et...
Soit les variables . La distance entre deux variables est définie comme. La distance entre deux littéraux est la distance entre les deux variables correspondantes. d ( x a , x b ) = | a - b |X1, x2, x3. . . Xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nré( xune, xb) = | a - b |d(xa,xb)=|a−b|d(x_a , x_b) =...
Suite à une question précédente , quelles sont les meilleures limites inférieures de l' espace actuel pour SAT? Avec une borne inférieure d'espace, je veux dire ici le nombre de cellules de bande de travail utilisées par une machine Turing qui utilise un alphabet binaire de bande de travail. Un...
Quelqu'un pourrait-il indiquer un ou plusieurs sites Web où il est possible de télécharger une implémentation fonctionnelle d'un solveur #SAT? Je suis intéressé par ceux qui renvoient le nombre exact de solutions, pas une
Le problème de décision CNF-SAT peut être décrit comme suit: Entrée: Une formule booléenne ϕϕ\phi sous forme normale conjonctive. Question: Existe-t-il une affectation de variable qui satisfait ϕϕ\phi ? J'envisage plusieurs approches différentes pour résoudre CNF-SAT avec une machine de Turing à...
Je suis actuellement intéressé à obtenir (ou construire) et à étudier des formules 3-CNF insatisfaisantes et de taille minimale. Autrement dit, elles doivent être constituées du moins de clauses (m = 8 de préférence) et de autant de variables distinctes (n = 4 ou plus) que possible, de sorte que la...
Le problème Max-Sat vous demande de trouver une affectation d'une formule CNF qui satisfasse autant de clauses que possible. Pour le problème SAT plus simple, il existe de nombreux cas spéciaux connus qui peuvent être résolus en temps polynomial, par exemple, nous pouvons résoudre 2-SAT en temps...
Soit une formule CNF satisfaisante avec n variables et m clauses. Soit S F 1 l'espace de solution de F 1 .F1F1F_1nnnmmmSF1SF1S_{F_1}F1F1F_1 Considérons le problème de déterminer, étant donné , une autre formule CNF F 2 avec le même ensemble de variables que F 1 , avec S F 2 = S F 1 (même espace de...
Ici, l'objectif est de réduire un problème SAT arbitraire à 3-SAT en temps polynomial en utilisant le moins de clauses et de variables. Ma question est motivée par la curiosité. Moins formellement, j'aimerais savoir: "Quelle est la réduction" la plus naturelle "du SAT au 3-SAT?" Maintenant, la...
Le problème de satisfaction est, bien sûr, un problème fondamental en CS théorique. Je jouais avec une version du problème avec une infinité de variables. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Configuration de base. Soit XXX un ensemble de variables non vide et...
Des travaux ont-ils été effectués sur la façon dont la complexité des instances aléatoires de # 2-SAT varie avec la densité de la clause? C'est-à-dire: comment la difficulté de compter des solutions satisfaisantes pour une instance générée aléatoirement de 2-SAT varie-t-elle, comme la densité de...
Existe-t-il des algorithmes de résolution SAT qui ne sont pas basés sur DPLL? Ou tous les algorithmes utilisés par les solveurs SAT sont-ils basés sur
Dans le passé, j'ai implémenté des modèles de coordination utilisant SAT et la satisfaction des contraintes régulières comme cheval de bataille principal dans leurs moteurs. Poursuivant dans cette ligne de travail, je voudrais rendre les modèles plus interactifs, et la meilleure façon que je vois...
Étant donné , combien de -DNF avec variables et clauses sont tautologiques? (ou combien de -CNF ne sont pas satisfaisants?)k n m km , n , km,n,km, n,
Version courte. La preuve originale que # 2-SAT est #P -complete montre, en fait, que les instances de # 2-SAT qui sont à la fois monotones (n'impliquant la négation d'aucune variable) et bipartites (le graphique formé par les clauses sur le est un graphe bipartite) sont #P -hard. Ainsi, les deux...
Il est bien connu que les formules aléatoires -CNF sur n variables avec c n clauses sont insatisfaisantes (c'est-à-dire qu'elles sont des contradictions) avec une probabilité élevée, pour une constante c suffisamment grande . Ainsi, les formules k -CNF aléatoires (pour c assez grand) constituent...
Par un résultat classique de Kuroda, la classe de complexité NSPACE [ ]nnn (également connue sous le nom de NLIN-SPACE) est précisément la classe CSL des langages contextuels . Le problème de satisfiabilité SAT est dans NSPACE [ ], car une estimation de taille linéaire pour une solution peut être...