SAT signifie le problème de satisfiabilité booléenne.
Quelles sont les meilleures limites inférieures actuelles pour le temps et la profondeur de circuit pour
Dans un autre fil de discussion , Joe Fitzsimons s'est interrogé sur "la meilleure limite inférieure actuelle de 3SAT". J'aimerais faire l'inverse: quelle est la meilleure limite supérieure actuelle sur 3SAT? En d'autres termes, quelle est la complexité temporelle du solveur SAT le plus efficace?...
Quelles sont les explications théoriques à la réussite pratique des solveurs SAT, et quelqu'un peut-il donner un aperçu et des explications de type "wikipedia"? Par analogie, l' analyse lissée ( version arXiv ) de l'algorithme simplex explique très bien pourquoi elle fonctionne si bien dans la...
Dans cette question, une formule 3CNF signifie une formule CNF où chaque clause implique exactement trois variables distinctes . Pour un 0 < s <1 constant , Gap-3SAT s est le problème de promesse suivant: Gap-3SAT de l' instance : A 3CNF formule de φ. Oui-promesse : φ est satisfaisable. Pas...
Décider si une formule booléenne quantifiée telle que ∀ x1∃ x2∀ x3⋯ ∃ xnφ ( x1, x2, … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), évalue toujours à true est un problème classique PSPACE-complete. Cela peut être considéré...
Quelqu'un ose-t-il tenter de clarifier quelle est la relation de ces domaines d'études ou peut-être même donner une réponse plus concrète au niveau des problèmes? Comme qui comprend qui en supposant certaines formulations largement acceptées. Si j'ai bien compris, lorsque vous passez de SAT à SMT,...
Définir ioioio - SUBEXPSUBEXPSUBEXP comme étant la classe de langues LLL telle qu'il existe une langue L′∈∩ε>0TIME(2nε)L′∈∩ε>0TIME(2nε)L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}}) et pour une infinité de nnn , LLL et L′L′L' accord sur toutes les instances de longueur nnn ....
J'ai entendu dire qu'il existe des arguments heuristiques en physique statistique qui donnent des résultats dans la théorie des probabilités pour lesquels des preuves rigoureuses sont inconnues ou très difficiles à obtenir. Quel est un simple exemple de jouet d'un tel phénomène? Ce serait bien si...
Les algorithmes classiques peuvent résoudre le 3-SAT en temps (randomisé) ou 1,3303 n temps (déterministe). (Référence: Best Upper Bounds on SAT )1,3071n1.3071n1.3071^n1.3303n1.3303n1.3303^n À titre de comparaison, l'utilisation de l'algorithme de Grover sur un ordinateur quantique rechercherait et...
Considérons le problème 3-SAT sur n variables. Le nombre de clauses distinctes possibles est le suivant: C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. Le nombre de cas de problème est le nombre de tous les...
Le blog de Scott Aaronson a donné aujourd'hui une liste de problèmes / tâches ouverts intéressants en complexité. Un en particulier a retenu mon attention: Construisez une bibliothèque publique d'instances 3SAT, avec aussi peu de variables et de clauses que possible, qui aurait des conséquences...
Vous pouvez souvent trouver des méthodes de plan de coupe, de propagation variable, de branchement et de limite, d'apprentissage de clause, de retour en arrière intelligent ou même d'heuristique humaine tissée à la main dans les solveurs SAT. Pourtant, pendant des décennies, les meilleurs solveurs...
Que sont les "régions faciles" pour la satisfiabilité? En d'autres termes, des conditions suffisantes pour qu'un solveur SAT puisse trouver une affectation satisfaisante, en supposant qu'elle existe. Un exemple est lorsque chaque clause partage des variables avec quelques autres clauses, en raison...
En lisant l'article "Est-il temps de déclarer la victoire en comptant la complexité?" sur le blog "Godel's Lost Letter and P = NP" , ils ont mentionné la dichotomie pour les CSP. Après quelques liens après, googler et wikipeding, je suis tombé sur le théorème de Ladner : Théorème de Ladner: Si ,...
Est-il possible de traduire une formule booléenne B en une conjonction équivalente de clauses Horn? L'article de Wikipédia sur HornSAT semble impliquer que c'est le cas, mais je n'ai pu chasser aucune référence. Notez que je ne veux pas dire "en temps polynomial", mais plutôt "du...
Certains problèmes NP-durs qui sont exponentiels sur les graphes généraux sont sous-exponentiels sur les graphes planaires car la largeur de l'arborescence est au maximum de et ils sont exponentiels dans la largeur de l'arborescence.4.9|V(G)|−−−−−−√4.9|V(G)|4.9 \sqrt{|V(G)|} Fondamentalement, je...
Je m'intéresse à la densité critique de 3-satisfiabilité (3-SAT) . On suppose qu'un tel α existe: si le nombre de clauses 3-SAT générées aléatoirement est ( α + ϵ ) n ou plus, elles sont presque sûrement insatisfaisantes. (Ici, ϵ est une petite constante et n est le nombre de variables.) Si le...
Pour une formule 3CNF laisser soit le nombre de maximal de clauses satisfaites dans toute affectation à . On sait que Max-3SAT est difficile à estimer (sous réserve de P ≠ NP), c'est-à-dire qu'il n'y a pas d'algorithme de polytime dont l'entrée est une formule 3CNF , et dont la sortie est le nombre...
Une caractéristique bien connue des instances -SAT est le rapport du nombre de clauses sur le nombre de variables n , c'est-à-dire le quotient \ rho = m / n . Pour chaque k , il existe une valeur seuil \ alpha st \ pour \ rho \ ll \ alpha , la plupart des instances sont satisfaisables et pour \ rho...
Les solveurs SAT sont très importants dans les attaques algébriques , par exemple les marches et les minisat . Cependant, lors de la résolution des problèmes de référence disponibles ici, il existe une énorme différence de performances entre les deux - Walksat est beaucoup plus rapide que minisat...