Eine quantitative Messung der Ressourcen, die benötigt werden, um Widersprüche im propositionalen Resolution-Beweissystem zu erzeugen, typischerweise beschrieben durch Parameter wie Beweislänge (Anzahl abgeleiteter Klauseln), Breite (maximale Klauselgröße) und Raum (Speicher gemessen an gleichzeitig gehaltenen Klauseln).

Prinzip

Die Resolution-Komplexität ordnet die Härte, indem sie verfolgt, wie Einschränkungen der Beweisressourcen zu längeren oder breiteren Widerlegungen zwingen; Trade-offs zwischen Länge, Breite und Raum bestimmen die Schwierigkeit, unerfüllbare Formeln per Resolution zu widerlegen.

Demonstration

Konkretes Beispiel: propositionale Kodierungen des Schubfachprinzips besitzen nur Resolution-Beweise, deren Länge exponentiell mit der Anzahl der Objekte wächst; Breitenuntergrenzen können verwendet werden, um entsprechende Längenuntergrenzen für diese Formelklassen zu beweisen.

Fehlanwendung

Die Resolution-Komplexität mit allgemeiner algorithmischer Zeitkomplexität gleichzusetzen oder anzunehmen, dass Unterschriftsgrenzen in Resolution ohne Weiteres auf beliebige Beweissysteme oder SAT-Solver übertragbar sind, ohne Simulationsrelationen und Heuristiken zu berücksichtigen.

Konsequenz

Bei korrekter Anwendung liefert sie strenge Untergrenzen für die Beweissuche, erklärt, warum SAT-Solver bei bestimmten Formelklassen versagen, und leitet die Gestaltung von Beweissystemen und Heuristiken, indem sie aufzeigt, welche Ressource der Engpass ist.

Umkehrung

Dreht man die Perspektive um und fragt, welche Formeln kurze, schmale und raumarme Resolution-Beweise besitzen, so hebt die Umkehrung handhabbare Teilklassen und konstruktive Beweisstrategien hervor statt Härte.

Abgrenzung

Gilt speziell für das propositionale Resolution-Beweissystem (und eng verwandte Klausellernverfahren); sie misst nicht unmittelbar Beweise in Sequenzenkalkülen, Frege-Systemen oder semantischen Widerlegungen, es sei denn, es sind explizite Simulationen gegeben.

Semantische Spannung

Steht in Spannung zur allgemeineren Bezeichnung Beweis-Komplexität (die viele Beweissysteme umfasst) und zu syntaktischen Maßen wie Schaltkreisgröße; die Resolution-Komplexität ist enger gefasst, aber oft zugänglicher für kombinatorische Untergrenztechniken.

Synthese

Resolution-Komplexität fasst die quantitativen Parameter (Länge, Breite, Raum) zusammen, die die Kosten für das Herleiten von Widersprüchen in Resolution charakterisieren; durch Studium der Trade-offs dieser Parameter lassen sich präzise Erklärungen propositionaler Härte und Hinweise für Solver-Design gewinnen.