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...
Est-il possible que ? Y a-t-il des conséquences intéressantes d'un tel confinement? Cela contredirait-il l'hypothèse du temps exponentiel?SAT¯¯¯¯¯¯¯¯¯¯∈NTIME(exp(n0.9))SAT¯∈NTIME(exp(n0.9))\overline{SAT} \in
Je partie d'une tentative de preuve . La tentative de preuve consiste en une réduction Karp du ⊕ P problème -complete ⊕ 3 RÉGULIER COUVERTURE vertex SAT.⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Étant donné un graphique cubique , la réduction produit une formule...
Tous les solveurs #SAT que je connais, par exemple RelSat, C2D, ne renvoient que le nombre d'instances satisfaisables. Mais je veux connaître chacun de ces cas? Existe-t-il un tel solveur #SAT ou comment dois-je modifier un solveur #SAT disponible pour ce faire? Je vous
Quels sont les obstacles à la compétitivité des solveurs SAT avec des algorithmes de graphes spécialisés? En d'autres termes, est-il possible de s'attendre à des solveurs SAT qui peuvent remplacer le rôle de concepteur d'algorithmes - c'est-à-dire être capables de reconnaître automatiquement la...
Existe-t-il un résultat connu sur la classe de complexité de 1-en-3-SAT avec un nombre restreint d'occurrences variables? J'ai trouvé la réduction parcimonieuse suivante avec Peter Nightingale, mais je veux citer quelque chose si cela est connu. Voici l'astuce que nous avons trouvée. Cela montre...
Je m'intéresse à une variation SAT où la formule CNF est monotone (aucune variable n'est niée). Une telle formule est évidemment satisfaisable. Mais disons que le nombre de vraies variables est une mesure de la qualité de notre solution. Nous avons donc le problème suivant: VÉRITABLE MONOTONE 3SAT...
Je développe un algorithme SAT depuis un certain temps et j'ai atteint un point où j'aimerais le partager. Je ne connais pas beaucoup de gens en informatique et je ne sais pas exactement vers qui me tourner. Je me demande quelles ressources sont disponibles pour quelqu'un avec un algorithme qui...
Impagliazzo, Paturi et Calabro, Impagliazzo, Paturi ont introduit l'hypothèse de temps exponentiel (ETH) et l'hypothèse de temps fortement exponentiel (SETH). En gros, SETH dit qu'il n'y a pas d'algorithme qui résout SAT dans le temps . 1,99n1.99n1.99^n Je me demandais ce que cela signifierait pour...
Soit un vecteur de variables booléennes. Soit C , D deux circuits booléens sur x . Disons que C est similaire à D si:x = ( x1, … , Xn)x=(x1,…,xn)x=(x_1,\dots,x_n)C, DC,DC,DXxxCCCréDD est exponentiellement petit, lorsque x est tiré uniformément au hasard à partir de { 0 , 1 } n (en d'autres termes,...
Ce récent article de FOCS2013, Strong Backdoors to Bounded Treewidth SAT par Gaspers et Szeider parle du lien entre la largeur d' arbre du graphe de la clause SAT et la dureté de l'instance. Pour les instances 3-SAT aléatoires, c'est-à-dire les instances 3-SAT choisies au hasard, quelle est la...
Quelle est la définition standard de Planar 3-SAT? J'ai vu un certain nombre de définitions différentes. Quel est le document original qui l'a défini et a prouvé qu'il était
Une langue est dans la classe D P ssi il y a deux langues L 1 ∈ N P et L 2 ∈ c o N P telles que L = L 1 ∩ L 2LLLD PDPDPL 1 ∈ NPL1∈NPL1 \in NPL 2 ∈ c o NPL2∈coNPL2 \in coNPL = L 1 ∩ L 2L=L1∩L2L = L1 \cap L2 A canonique problème -complete est SAT-UNSAT: étant donné deux expressions 3-CNF, F et G ,...
Elberfeld, Jakoby et Tantau 2010 ( ECCC TR10-062 ) se sont révélés une version peu encombrante du théorème de Bodlaender. Ils ont montré que pour les graphiques avec une largeur d'arbre au plus , une décomposition d'arbre de largeur k peut être trouvée en utilisant l'espace logarithmique. Le...
Supposons que nous considérons 3-SAT avec des variables et des clauses . Je recherche une méthode qui semble prendre temps / espace pour résoudre tout problème SAT correspondant à cette description, à l'intérieur d'une erreur qui peut être ajustée à un montant arbitraire. Cependant, il y a un hic.c...
Un problème CNF SAT NP est-il difficile lorsque le nombre total (mais pas la largeur) des clauses de 3 termes ou plus est limité au-dessus par une constante? Qu'en est-il spécifiquement quand il n'y a qu'une seule clause de ce
Je m'intéresse aux instances individuelles "dures" de problèmes NP-complets. Ryan Williams a discuté du problème SAT0 sur le blog de Richard Lipton . SAT0 demande si une instance SAT a la solution spécifique composée de tous les 0. Cela m'a fait penser à la construction d'instances SAT susceptibles...
Cette question s'est posée dans mon esprit après avoir lu les contributions d'András Salamon et Colin McQuillan à ma question précédente Compter les solutions des formules Monotone-2CNF . EDIT 30 e mars 2011 question n ° 2. Ajouté EDIT 29 e octobre 2010 Question reformulée après proposition András...
Je voudrais connaître l'état actuel de la transition de phase pour les k-sat aléatoires, étant donné n variables et m clauses, quel est le c = m / n le mieux connu pour les bornes supérieures et
Je souhaite réduire -Clique en SAT sans agrandir l'instance.kkk La clique est en NP, elle peut donc être réduite à SAT en utilisant l'espace logarithmique. La réduction simple des manuels de Garey / Johnson fait exploser l'instance à la taille cubique . Cependant, -Clique est en P pour chaque fixe...