Qu'est-ce que SAT et à quoi cela sert-il?

Question

Récemment, j'ai vu un article Reddit sur l'utilisation de SAT pour résoudre un puzzle [1]. Cela m'a fait très curiosités à propos de cette chose "Sat". J'ai lu l'article Wikipedia mais je voudrais vous demander à quelqu'un de l'expliquer en termes plus profane.

Qu'est-ce que SAT et à quoi sert-il? Peut-il être utilisé pour traverser une structure d'arbres? Pour l'analyse des textes? Pour la rupture de ligne [2]? Pour l'emballage des poubelles [3]? Est-ce une sorte de technique d'optimisation?

Sur une note connexe, j'ai lu que NP vs P consiste à choisir les nombres d'une somme définie sur zéro vs vérifiant si certains nombres résument à zéro - SAT est-il en quelque sorte lié à cela?

[1] http://www.reddit.com/r/programming/comments/pxpzd/solving_hexiom_really_fast_with_a_sat_solver/

[2] http://en.wikipedia.org/wiki/line_wrap

[3] http://en.wikipedia.org/wiki/bin_packing_problemband

Answer 1

SAT est très important car il est complet NP. Pour comprendre ce que cela signifie, vous avez besoin d'une notion claire de classes de complexité. Voici un court aperçu:

• P est la classe de tous les problèmes qui peuvent être résolus en temps polynomial (c'est-à-dire rapidement).

• NP est la classe de tout problème pour lequel une solution peut être vérifiée en temps polynomial. Cela signifie que le fait qu'une solution donnée est rapide est rapide, mais en trouver un est généralement lent (le plus souvent le temps exponentiel). À moins que le problème ne soit dans la partie P de NP bien sûr (comme indiqué ci-dessous P fait partie de NP, comme vous pouvez facilement le vérifier).

Ensuite, il y a l'ensemble de problèmes NP-Complete. Cet ensemble contient tout un problème qui est si générique, vous pouvez résoudre ces problèmes au lieu d'un autre de NP (cela s'appelle Réduire un problème sur un autre). Cela signifie que vous pouvez transformer un problème à partir d'un domaine en un autre problème NP-complete, lui faire dériver une réponse et transformer la réponse.

Souvent, cependant, il peut être prouvé qu'un problème est complet NP, mais les transformations ne sont pas claires pour un autre problème donné.

SAT est tellement agréable, car il est complet NP, c'est-à-dire que vous pouvez le résoudre au lieu de tout autre problème en NP, et les réductions ne sont pas si difficiles à faire. Le TSP est un autre problème NP-Complete, mais les transformations sont le plus souvent beaucoup plus difficiles.

Donc, oui, SAT peut être utilisé pour tous ces problèmes que vous mentionnez. Souvent, cependant, ce n'est pas possible. Là où il est possible, c'est quand aucun autre algorithme rapide n'est connu, comme le puzzle que vous mentionnez. Dans ce cas, vous n'avez pas à développer un algorithme pour le puzzle, mais vous pouvez utiliser l'un des solveurs SAT hautement optimisés et vous vous retrouverez avec un algorithme rapide raisonnable pour votre puzzle.

Traverser une structure d'arbre est si simple par exemple, que toute transformation et à SAT sera très probablement beaucoup plus complexe que d'écrire directement la traversée directement.

Answer 2

Pour faire une longue histoire, un solveur SAT est quelque chose à laquelle vous donnez une formule booléenne, et il vous indique s'il peut trouver une valeur pour les différentes variables telles que la formule est vraie.

Exemple

supposer que a, b et c sont des variables booléennes, et vous voulez savoir si ces variables peuvent se voir attribuer une valeur qui fait en quelque sorte la formule (¬a ∨ b) ∧ (¬b ∨ c). Vous envoyez cette formule au solveur SAT, et il vous retournera true. Les solveurs SAT vous donnent également souvent une affectation valide. Dans ce cas, cette affectation pourrait être a: false, b:false, c:false.

À quoi peut-il être utilisé?

Je ne l'utiliserais pas pour traverser les arbres ni pour analyser du texte ou pour casser les lignes. Cependant, vous pouvez l'utiliser lors de la traversée d'un arbre pour vérifier si certaines contraintes sur l'arbre sont satisfaites. Vous pouvez certainement l'utiliser pour l'emballage des poubelles, même si certains solveurs CSP spécialisés fonctionneront probablement mieux sur ce type de problèmes.

Les solveurs SAT deviennent beaucoup plus courants de nos jours, en particulier dans les logiciels comme les gestionnaires de packages. Eclipse incorpore SAT4J pour gérer les dépendances entre ses plugins. D'autres applications de SAT incluent généralement la vérification du modèle, les applications de planification, les configurateurs, la planification et bien d'autres.