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...
Les solveurs SAT offrent un moyen puissant de vérifier la validité d'une formule booléenne avec un quantificateur. Par exemple, pour vérifier la validité de , nous pouvons utiliser un solveur SAT pour déterminer si φ ( x ) est satisfaisable. Pour vérifier la validité de ∀ x . φ ( x ) , nous pouvons...
Si , alors il y a un algorithme de logspace qui résout la version de décision de 2-SAT.L=NLL=NL\mathsf{L = NL} Est-il connu que implique qu'il existe un algorithme d'espace de journalisation pour obtenir une affectation satisfaisante , lorsqu'il reçoit une instance 2-SAT satisfaisante en...
Cette question est étroitement liée à un autre article: Transitions de phase dans les problèmes difficiles NP, mais elle est quelque peu différente. Bien que cette question concerne la dureté d'instances particulières de problèmes difficiles NP, il s'agit de classer la difficulté des mêmes...
Soit une formule CNF avec n variables et m clauses. Soit t ∈ { 0 , 1 } n une affectation de variable et f φ ( t ) ∈ { 0 , … , m } compte le nombre de clauses satisfaites par une affectation de variable à φ . Définissez ensuite Median-SAT comme le problème du calcul de la valeur médiane de f φ ( t )...
Le problème #SAT est le problème canonique # P-complete. C'est un problème de fonction plutôt qu'un problème de décision. Il demande, étant donné une formule booléenne dans la logique propositionnelle, combien d'affectations satisfaisantes F a. Quelles sont les meilleures limites inférieures sur...
Le rapport critique des clauses aux variables pour le 3-SAT aléatoire est supérieur à 3 et inférieur à 6, et semble être communément décrit comme «autour de 4,2» ou «autour de 4,25». Mezard, Parisi et Zecchina prouvent (au sens physique) que le rapport critique est 4.256, tandis que les premier et...
J'ai recherché sur Internet, mais je n'ai trouvé aucune «grande liste» de variantes du problème SAT. Mis à part le (commun) SAM, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT Quelles sont les autres variantes? (cela sera également très utile si des classes de complexité sont données (si...
Y aurait-il des conséquences majeures si SAT avait tout au plus des preuves non-exponentielles sous-exponentielles ou encore plus fortement, SAT avait des algorithmes de temps
Une formule Monotone-2CNF est une formule CNF où chaque clause est composée d'exactement 2 littéraux positifs. Maintenant, j'ai une formule Monotone-2CNF FFF. Soit SSS l'ensemble des affectations satisfaisantes de FFFJ'ai également un oracle qui est capable de donner les informations suivantes:OOO...
Rappelons que la largeur d'une résolution réfutation RRR d'une formule CNF FFF est le nombre maximal de littéraux dans une clause se produisant dans RRR . Pour chaque www , il existe des formules insatisfaisantes FFFdans 3-CNF st chaque réfutation de résolution de FFF nécessite une largeur d'au...
dans le Bundeswettberweb Infomatik 2010/2011, il y avait un problème intéressant: Pour fixe , trouver un k minimal et une carte φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , de sorte qu'il n'y a pas de triple ( i , j ) , ( i + l , j ) , ( i + l , j + l ) avec φ ( innnkkkφ : { ( i , j ) | i ≤ j ≤...
Selon cet article , qui discute d'une extension non déterministe de l' hypothèse de temps exponentiel fort (SETH), "[…] Williams a récemment montré que les hypothèses liées à la complexité de Merlin-Arthur de k-TAUT sont fausses". Cependant, ce document ne cite qu'une communication personnelle....
Nous savons que le problème du comptage du nombre d'affectations satisfaisantes dans une formule booléenne générale donnée (CNF-SAT), une formule DNF donnée, ou même une formule 2SAT donnée est un problème # P-complet . Maintenant, considérons un CNF-SAT sans littéral négatif (pas de , toujours A...
Je commence à étudier la possibilité de compter sur un solveur SAT pour résoudre un problème d'optimisation qui m'intéresse, et je suis actuellement à la recherche d'une enquête qui présenterait des exemples de transformations "intelligentes" vers des variantes de SAT (c'est-à-dire des...
Il est bien connu que les formules CNF peuvent être grossièrement partitionnées en 2 grandes classes: aléatoire vs structurée. Les formules CNF structurées, contrairement aux formules CNF aléatoires, présentent une sorte d'ordre, montrant des modèles qui ne se produiront probablement pas par...
Comment montrer qu'une certaine propriété ne peut pas être exprimée en 2-CNF (2-SAT)? Existe-t-il des jeux, tels que des jeux de galets? Il semble que le jeu de galets noir classique et le jeu de galets noir et blanc ne conviennent pas à cela (ils sont complets sur PSPACE, selon Hertel et Pitassi,...
Il existe 4 contraintes différentes que nous pouvons avoir lors de la définition de K-SAT aléatoire. 1) Le nombre total de littéraux dans une clause donnée est exactement K ou AT la plupart des K 2) Un littéral donné peut être utilisé avec ou sans remplacement dans la même clause (A ou A ou A) 3)...
J'examine le langage de toutes les formules logiques propositionnelles satisfaisantes, SAT (pour garantir qu'il ait un alphabet fini, nous encoderions les lettres propositionnelles d'une manière appropriée [modifier: les réponses ont souligné que la réponse à la question peut ne pas être robuste...
Le SAT unique est le problème bien connu: étant donné une formule CNF , est-il vrai que F a exactement un modèle?FFFFFF Je m'intéresse au problème «Exactement -SAT»: étant donné une formule CNF F et un entier m > 1 , est-il vrai que F a exactement m modèles?mmmFFFm>1m>1m>1FFFmmm Les deux...