Mesure quantitative des ressources nécessaires pour produire des réfutations dans le système de preuve propositionnel par résolution, généralement exprimée par des paramètres tels que la longueur de la preuve (nombre de clauses dérivées), la largeur (taille maximale d'une clause) et l'espace (mémoire mesurée par le nombre de clauses conservées simultanément).

Principe

La complexité de résolution organise la difficulté en suivant comment les contraintes sur les ressources de preuve contraignent à des réfutations plus longues ou plus larges ; des compromis entre longueur, largeur et espace déterminent la difficulté de réfuter des formules insatisfaisables en résolution.

Démonstration

Exemple concret : les codages propositionnels du principe des tiroirs n'admettent que des réfutations en résolution dont la longueur croît exponentiellement avec le nombre de pigeons ; des minorations de la largeur permettent d'établir des minorations correspondantes de la longueur pour cette famille de formules.

Mauvaise application

Prendre la complexité de résolution pour équivalente à la complexité temporelle algorithmique générale ou supposer que des bornes inférieures en résolution se transfèrent immédiatement à des systèmes de preuve quelconques ou à des solveurs SAT sans considérer les relations de simulation et les heuristiques.

Conséquence

Une application correcte fournit des bornes inférieures rigoureuses sur la recherche de preuves, explique pourquoi les solveurs SAT échouent sur certaines familles de formules et oriente la conception de systèmes de preuve et d'heuristiques en révélant quelle ressource est le goulot d'étranglement.

Inversion

Inverser la perspective en se demandant quelles formules admettent des réfutations en résolution courtes, étroites et peu gourmandes en espace ; l'inversion met en lumière des sous-classes traitables et des stratégies constructives de preuve plutôt que la difficulté.

Limite

S'applique spécifiquement au système de preuve propositionnel par résolution (et aux procédures proches, comme l'apprentissage de clauses) ; elle ne mesure pas directement les preuves dans les calculs de séquents, les systèmes de Frege ou des réfutations sémantiques sauf si des simulations explicites sont établies.

Tension sémantique

Entre en tension avec la notion plus large de complexité des preuves (qui couvre de nombreux systèmes) et avec des mesures syntaxiques comme la taille de circuit ; la complexité de résolution est plus étroite mais souvent plus accessible aux techniques combinatoires de bornes inférieures.

Synthèse

La complexité de résolution réunit les paramètres quantitatifs (longueur, largeur, espace) qui caractérisent le coût pour dériver une contradiction en résolution ; l'étude des compromis entre ces paramètres fournit des explications précises de la difficulté propositionnelle et des orientations pour la conception de solveurs.