La satisfaction (SAT) est le problème de déterminer s'il existe une affectation de variable qui répond à une formule booléenne donnée.
Étant donné une instance de SAT, je voudrais pouvoir estimer à quel point il sera difficile de résoudre l'instance. Une façon consiste à exécuter des solveurs existants, mais ce genre de résultat va à l'encontre du but d'estimer la difficulté. Une deuxième façon pourrait être de regarder le rapport...
J'utilise un solveur SAT pour coder un problème, et dans le cadre de l'instance SAT, j'ai des variables booléennes x1,x2,…,xnx1,x2,…,xnx_1,x_2,\dots,x_n où il est prévu que l'une d'entre elles soit vraie et que le reste soit être faux. (J'ai parfois vu cela décrit comme un encodage "à chaud".) Je...
Soit une formule booléenne composée des opérateurs ET, OU et NON habituels et de certaines variables. Je voudrais compter le nombre de missions satisfaisant pour . Autrement dit, je veux trouver le nombre d'affectations différentes de valeurs de vérité aux variables de pour lesquelles suppose une...
Ce que je veux faire, c'est transformer un problème mathématique que j'ai en un problème de satiabilité booléenne (SAT), puis le résoudre à l'aide d'un solveur SAT. Je me demande si quelqu'un connaît un manuel, un guide ou quelque chose qui m'aidera à convertir mon problème en une instance SAT....
WalkSAT et GSAT sont des algorithmes de recherche locale simples et bien connus pour résoudre le problème de satisfiabilité booléenne. Le pseudocode de l'algorithme GSAT est copié de la question Mise en œuvre de l'algorithme GSAT - Comment sélectionner le littéral à retourner? et présenté...
Récemment, j'ai trouvé dans un article [1] une version symétrique spéciale de SAT appelée 2/2/4-SAT . Mais il existe de nombreuses variantes complètes, par exemple: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NPNP\text{NP} Quelques autres variantes sont traitables: - , Planar-NAE- , ...SAT...
L'algorithme GSAT est, pour la plupart, simple: vous obtenez une formule sous forme normale conjonctive et retournez les littéraux des clauses jusqu'à ce que vous trouviez une solution qui satisfasse la formule ou que vous atteigniez la limite max_tries / max_flips et ne trouviez aucune solution....
Comment puis-je prouver que la conversion de CNF en DNF est NP-difficile? Je ne demande pas de réponse, juste quelques suggestions sur la façon de le
J'ai un problème de décision NP-complet. Étant donné une instance du problème, je voudrais concevoir un algorithme qui génère OUI, si le problème est réalisable, et NON, sinon. (Bien sûr, si l'algorithme n'est pas optimal, il fera des erreurs.) Je ne trouve aucun algorithme d'approximation pour de...
Après la sortie de la bibliothèque AIGER pour gérer les graphiques et les onduleurs en 2006 (je pense), certains solveurs SAT de circuits ont été publiés en 2006-2008, et dans quelques courses / compétitions SAT, il y avait des pistes AIG. Cependant, depuis lors, il semble que l'accent ait été...
Les solveurs SAT sont de plus en plus efficaces dans la résolution de grandes instances et sont utilisés comme back-end dans divers contextes. Chaque fois que l'on veut les utiliser pour résoudre un problème dans un domaine spécifique, il / elle doit proposer un encodage ad hoc qui a non seulement...
On dit que le langage est dense s'il existe un polynôme tel que pour tous lesEn d'autres termes, pour une longueur donnée, il n'existe que de nombreux mots polynomiaux de longueur qui ne sont pas enJ⊆Σ∗J⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|Jc∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N.n \in...
J'essaie d'envelopper ma tête autour d'une preuve d'exhaustivité NP qui semble tourner autour de SAT / 3CNF-SAT. C'est peut-être l'heure tardive, mais je crains de ne pas pouvoir penser à une formule 3CNF qui ne puisse être satisfaite (il me manque probablement quelque chose d'évident). Pouvez-vous...
Ainsi, comme on le sait, le problème de décision 0-1 d'ILP est NP-complet. Il est facile de montrer qu'il est en NP, et la réduction d'origine provenait de SAT; depuis lors, de nombreux autres problèmes NP-Complete se sont révélés avoir des formulations ILP (qui fonctionnent comme des réductions de...
Supposons que l'on nous donne deux nombres et et que nous voulons trouver pour l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r L'algorithme naïf vérifie simplement toutes les paires possibles; par exemple en rubis, nous aurions: def max_xor(l, r) max = 0...
Planar 3SAT est NP-complet. Une instance planaire 3SAT est une instance 3SAT pour laquelle le graphique construit à l'aide des règles suivantes est planaire: ajouter un sommet pour chaque et ¯ x iXjeXjex_iXje¯Xje¯\bar{x_i} ajouter un sommet pour chaque clauseCjCjC_j ajouter un bord pour chaque...
Je suis sûr que quelqu'un a pensé à cela avant ou immédiatement rejeté, mais pourquoi la théorie de la dichotomie de Schaefer avec le théorème de Mahaney sur les ensembles clairsemés n'implique-t-elle pas P = NP? Voici mon raisonnement: créer un langage qui est égal à SAT intersecté par un ensemble...
Le problème SAT bien connu est défini ici à titre de référence. Le problème DOUBLE-SAT est défini comme DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has...
Quelle est la complexité de MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} et MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Sont-ils en P? Sont-ils durs en NP? Pour formaliser cela plus précisément, Φ ( x ) = ∧njeCje,Φ(X)=∧jenCje,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, où x =( x1, …...
C'est probablement une question stupide, mais je ne comprends tout simplement pas. Dans une autre question, ils ont proposé le théorème de dichotomie de Schaefer . Pour moi, il semble que cela prouve que chaque problème CSP est soit en P soit en NP-complet, mais pas entre les deux. Étant donné que...