Journal of the ACM · 1987 · 446 citations · 10 references
Super-resolution ImagingExpander GraphsHigh ResolutionEngineeringPropositional CalculusAutomated ReasoningPropositional LogicProof ComplexityFormal MethodsExponential Lower BoundsComputational ComplexityComputational ImagingComputer ScienceFirst-order LogicImage ResolutionSatisfiabilitySequent Calculus
Exponential lower bounds are proved for the length-of-resolution refutations of sets of disjunctions constructed from expander graphs, using the method of Tseitin. Since these sets of clauses encode biconditionals, they have short (polynomial-length) refutations in a standard axiomatic formulation of propositional calculus.
10
A Machine-Oriented Logic Based on the Resolution Principle
John A. Robinson · Journal of the ACM · 1965 · 3.9K citations · Full text
Introduction to Mathematical Logic.
Angelo Margaris, Alonzo Church · American Mathematical Monthly · 1957 · 932 citations
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 818 citations
Computational Complexity Theory, Engineering, Automated Reasoning +4