In the field of automated theorem proving, the efficiency of a logical calculus is traditionally measured by the length of the shortest proof it can generate. This metric relies on an implicit assumption: that the computational work required for each step is reasonably bounded. Reinhold Letz’s research, "On the Polynomial Transparency of Resolution," challenges this assumption by demonstrating that the resolution calculus—a foundational method in first-order logic—lacks "polynomial transparency."
The Problem: When Steps Do Not Equal Work
In computational logic, we often assume that if a proof has only a few steps, it is "easy" for a computer to process. This assumption is known as polynomial transparency: the idea that the actual computational work (time and memory) is bounded by a polynomial function of the input size and the number of inference steps.
If a calculus lacks this property, counting steps is deceptive. It is akin to counting the number of moves in a game without realizing that a single move might require calculating the trajectory of a billion particles. Letz investigates whether the resolution calculus—the engine behind many modern theorem provers—is truly transparent or if it hides exponential complexity within its individual steps.
A Framework for Transparency
To analyze this problem, the paper develops a formal framework to categorize the transparency of logical deductions:
- Polynomial Size-Transparency: Does the total size of the proof (the number of symbols) stay reasonably related to the elementary computing cost?
- Polynomial Step-Transparency: Can we measure the total cost just by looking at the input size and the number of inference steps?
- Weak Polynomial Transparency: Even if some proofs are "bloated," is there at least one shortest proof that remains computationally lean?
To test these categories, Letz constructs specific classes of logical formulas—specifically Horn formulas—designed to act as mathematical stress tests for the resolution rule.
The Renaming Trap
The primary reason resolution fails the transparency test is the renaming of variables. When deriving a new clause, variables must be given new names to avoid clashes. This mechanism allows a single resolution step to "hide" a massive increase in the complexity of the underlying data structure.
Letz demonstrates this through several examples:
- Exponential Growth: In certain formulas, "self-resolution" leads to clauses that grow exponentially in size ($> 2^k$) in just $k$ steps.
- Variable Explosion: Even when using optimizations like "number terms" (which represent repeated unary functions as a single unit), the introduction of binary function symbols causes a variable explosion that resolution cannot efficiently manage.
Key Results and Insights
The paper provides a formal proof that resolution for first-order logic is not polynomially transparent. Furthermore, it is not even weakly polynomially transparent. This is a significant blow to the practice of using "proof length" as a universal benchmark for resolution-based systems.
Key insights include:
- Shortest isn't always best: There are formulas where every possible resolution proof is exponentially large, even if the number of steps remains small.
- The Data Structure Limit: While moving from simple strings to Directed Acyclic Graphs (DAGs) can help manage formula size, Letz shows that even these advanced representations have limits when faced with complex functional structures.
- Complexity Gap: For certain formula classes, the physical size of a resolution refutation can be 25 times (or more) greater than the size of the input formula, while the step count remains misleadingly low.
Implications for Automated Reasoning
The results suggest that to truly understand the complexity of automated reasoning, the community may need to redefine what constitutes a "single inference step." Current metrics fail to reflect the actual physical resources—time and memory—required by theorem provers.
While the paper leaves it as an open problem whether a general data structure exists that can render resolution polynomially transparent for all first-order logic, it highlights a fundamental gap between theoretical proof length and practical computational cost. Future work must address the "binary function barrier" to ensure that our measures of efficiency match the reality of machine processing.
Summary updated