Complexity of Resolution Refutation

Complexity of Resolution Refutation

by Artificial Intelligence

Formal & Physical Sciences AI — News & Applications UYComputer scienceUYQArtificial intelligence (AI)
🎙 Artificial Intelligence 👥 3K 📅 February 4, 2016 ⏱ 40 min 👁 1K 📄 lecture 🧭 2026-08-18
Available in: English (current) Français

Keywords

resolutioncomplexityHorn clausesHerbrandSLD

Summary

This lecture discusses the computational complexity of resolution-based theorem proving. It begins by noting that while propositional logic is decidable, first-order logic is semi-decidable, and proof search can be infinite. The speaker cites Haken’s 1985 result showing that some propositional formulas require exponentially long proofs, and mentions Cook’s NP-completeness of SAT. To address these challenges, the lecture introduces Herbrand’s theorem, which allows reducing first-order logic to propositional logic by considering the Herbrand universe and base, though this may lead to infinite sets. Then, it presents two resolution strategies: unit preference and set of support, which aim to guide the search. The focus then shifts to Horn clauses, a subset of first-order logic with at most one positive literal per clause, which enables more efficient reasoning. The lecture explains the resolution table for Horn clauses and introduces SLD resolution, a linear strategy that corresponds to backward chaining and is the basis of Prolog. It concludes by noting that SLD resolution is complete for Horn clauses and that the user must write rules appropriately to exploit its efficiency.

176 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and structured overview of the complexity issues in resolution-based theorem proving. It effectively motivates the need for strategies and restricted languages by presenting key theoretical results (Haken, Cook) and then illustrating practical approaches (unit preference, set of support, Horn clauses). The argumentation is logical and builds upon previous knowledge, but it lacks formal proofs and relies on intuitive explanations. The value lies in its pedagogical clarity and the connection between theoretical complexity and practical strategies.

Scientific Rigor, Source Quality, Title Accuracy

The lecture mentions several key results and concepts: Haken’s 1985 result, Cook’s NP-completeness, Herbrand’s theorem, and SLD resolution. However, it does not provide specific citations or references, and the sources are not listed in the description. The title accurately reflects the content, which focuses on the complexity of resolution refutation. The presentation is rigorous in its logical flow, but the lack of explicit citations reduces the scientific rigor.

163 words

Title / Content Match

The title accurately reflects the content, which focuses on the computational complexity of resolution-based proof search.

Quality & Reliability

7/10

The lecture is based on established results (Haken 1985, Cook's NP-completeness, Herbrand's theorem) and standard resolution strategies. It is a didactic presentation without formal proofs, but the content is accurate and well-structured. The lack of citations and the informal style slightly reduce the score.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Contribution & Novelties

The lecture provides a clear pedagogical explanation of the complexity of resolution refutation, linking theoretical results (Haken, Cook) to practical strategies (unit preference, set of support) and restricted languages (Horn clauses). It emphasizes the trade-off between expressiveness and efficiency, and introduces SLD resolution as a linear strategy that underlies Prolog. The novelty lies in its integrative approach, connecting complexity theory, logic, and programming.

Pour aller plus loin :

  • Haken’s theorem — This Wikipedia article explains the exponential lower bound for resolution, which is a key result mentioned in the lecture.
  • NP-completeness — This article provides an overview of NP-completeness, including the SAT problem, which is central to the discussion of complexity.
  • Herbrand’s theorem — This article details Herbrand’s theorem and its implications for first-order logic.
  • Horn clause — This article defines Horn clauses and their properties, which are crucial for the lecture’s discussion.
  • SLD resolution — This article explains SLD resolution, a key concept for Prolog and logic programming.

159 words

Radar Profile

The radar profile shows high scores in quantity of information and technical level, indicating a dense and technical lecture. The quality of information and reliability are slightly lower, reflecting the lack of citations and formal proofs. Overall, the lecture is informative but could benefit from more rigorous sourcing.

Reliability 7/10