Abstract
Rough Resolution is a specialized refinement of the classic resolution principle designed to prune complex, or "large," literals from mathematical proofs. By resolving these expressions early, it allows instance-based theorem provers to avoid the combinatorial explosion of irrelevant data that often occurs in complex domains. This method enables the solution of challenge problems, such as LIM3, that have historically stumped general-purpose provers.
Introduction
In automated theorem proving, semantic hyper-linking is a prominent technique that generates ground instances of logical clauses to find an unsatisfiable set, thereby proving a theorem by contradiction. However, a significant bottleneck arises from the size of these instances. While most provers prioritize small, simple instances, many hard theorems—particularly in calculus—require very complex expressions. Standard provers often exhaust resources generating millions of irrelevant small instances before reaching the necessary complex ones. Rough Resolution addresses this by strategically deleting potentially large literals before the main search begins.
Methodology
The proposed method refines Robinson’s 1965 resolution principle by focusing on maximum literals—those guaranteed or likely to be the largest part of any clause instance.
Key Components
- Literal Identification: The algorithm distinguishes between absolute maximum literals (always the largest in any substitution) and likely maximum literals (those that may become the largest).
- Nuclei and Electrons: Utilizing terminology from classical logic methods, the algorithm treats clauses containing maximum literals as "nuclei." These are resolved simultaneously with "electron" clauses to eliminate the complex components.
- Growth Metric: To manage the generation of new clauses, a "growth" calculation prioritizes "negative growth" resolvents. This ensures that the resulting clauses are simpler or smaller than their parents, effectively quantifying progress.
- Hybrid Integration: Rough Resolution is designed as a collaborative tool. It removes large literals, while semantic hyper-linking handles smaller parts and UR-resolution manages logic-heavy (Horn) components.
Experimental Evaluation
The effectiveness of Rough Resolution was evaluated using a Prolog implementation on several benchmark sets from automated reasoning, including calculus challenges (LIM1-3), analysis theorems (IMV, AM8), and logic benchmarks (Lukasiewicz, ExQ).
Key Results
The empirical results demonstrate that Rough Resolution is a critical component for solving specific hard problems.
As shown in Table 1, Rough Resolution allowed the prover to solve the LIM3 problem in 534.8 seconds. Without this refinement, the process failed due to memory exhaustion or timeout (aborted after 20,000 seconds). Similarly, problems like AM8 and wos15 became solvable within reasonable timeframes. Notably, while specialized provers with built-in inequality rules can handle these cases, general-purpose provers like OTTER and CLIN were unable to solve any of the LIM+ problems at the time of the study.
Discussion and Future Work
Rough Resolution acts as a "surgical tool" to remove the most problematic parts of a logic problem. By measuring the multiset of literal sizes, the growth heuristic provides a formal way to overcome the "smallest-first" bias inherent in most provers. This allows the prover's natural bias toward small clauses to become an advantage once the "rough" literals are removed.
Limitations and Future Directions
Despite its successes, the method is "incomplete," meaning it cannot find every proof independently and must be paired with a complete method like semantic hyper-linking. Furthermore, even with growth metrics, "likely maximum literals" can lead to search space expansion if not managed carefully. The authors suggest extending the "rough" concept to paramodulation to handle equality axioms, which are notorious for containing complex literals that bog down provers.
Summary updated