Karl Lieberherr's old work on Non-Chronological Backtracking Based on Clause Learning

This web-page is the result of my interactions with the SAT/CSP/AI community after I informed them about my early work in the 1970's on clause learning from conflicts.

It was my fault not to publish my work properly back then (I published an ETH Zurich technical report in 1975 and a short AMS abstract in 1977 but the full details are only in my dissertation that is in German). The intent is not to accuse people that they should have built on my work but to point out where my work published in the 70s covered the same ideas as the newer works and how we can move the field forward now.

As Gerry Sussman wrote: "I think that the problem is that the mathematics world is very fragmented, so an idea written up in math journals is usually read by very few people." Back in the 1970's it was common to put a stake in the sand by publishing an abstract in the Notices of the AMS. I should have followed with a longer paper but my paper was rejected from computer science conferences like FOCS and STOC, the community I was in back then.

It is now clear that the CS community does not read mathematics abstracts. It was my fault that I did not publish my paper in an AI conference or journal. However, dissertations and technical reports from ETH Zurich also count as published works.

I wrote to several members prominent in the SAT/CSP/AI community. My claim is that superresolution is an early form of what is now considered to be clause learning with restarts. I got back many supporting statements and help with navigating the literature.

Here is an email exchange with Ashish Sabharwal, a 1995 PhD from the University of Washington, supervised by Paul Beame and Henry Kautz, who also saw this communication.

Feb 18, 2007 10:29 AM	 
SAT solvers and proof complexity

Hi Ashish:

thank you for your work on proof complexity and SAT solvers. 
Your papers state very clearly the results and I use the 
"harnessing the potential of clause learning" in my

Do you agree with the statements in:
? I was working in this area 30 years ago and discovered recently that there
is a lot of activity in "my" space. Please give me feedback on the above page.

From: Ashish Sabharwal ,
Cc: Paul Beame ,
    Henry Kautz 	 
Mar 6, 2007 4:12 PM	 
Re: SAT solvers and proof complexity

Dear Karl,

Thanks for the link to your 1977 paper on superresolution. I read the
paper, and it is indeed interesting work.

From what I understand, your main result relevant to our work is Lemma 3.1
on page 6 in your paper, which states that for every resolution proof R of
a formula, there is a shorter superresolution proof AR. This appears to be
almost a straightforward "observation" for superresolution, and, as you
mention, does match our relatively easy Theorem 2 concerning CL- with
unlimited restarts.


Comment by Karl:
I agree with you that my results were quite simple 
(compared to the P-optimal algorithm work I did simultaneously with Ernst Specker).

I needed many restarts because I used fine-grained P-optimal 
heuristics which dynamically influence the best variable ordering.

However, I needed to formalize clause learning back in 1977
so that I could state and prove theorems. Back then, developing
the succinct definition of superresolution was also a contribution.

Here is another example of such a statement:

Famous person 1 agreed: I am not surprised you already used it [clause learning based on conflict analysis] 30 years ago. Many results are "rediscovered" again and again. See e.g. all the work that has already been done in the 80s, early 90s about SAT in *J. Gu, P. W. Purdom, J. Franco, and B. W. Wah, in "Satisfiability Problem: Theory and Applications", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1997, pp. 19-152. (reference 348 [Lieberherr/Specker] in the above paper is about the sister technique that we developed after superresolution.)

However, I got back one contradictory statement:

Famous person 2 disagreed: My interpretation is that your 1977 AMS paper does not address clause learning from conflicts. ... I kindly ask you not to send me further email messages on this subject. I do not want to get involved in further discussions on this issue.

I believe I convinced Famous person 2 that Famous person 1 is right. But I was quite surprised by the defensiveness of Famous person 2.

As part of the argument to convince famous person 2 I wrote: Superresolution and Comparison and Gerald Sussman's view and My PhD Dissertation (1977).

It does not matter who was first but how we can progress the state-of-the-art now (an insight by Gerry Sussman). That is why we wrote a new paper on this topic in 2007 Integrating Superresolution with P-Optimal Algorithms.