Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!bloom-beacon!eru!luth!sunic!dkuug!daimi!kimskak
From: kimskak@daimi.dk (Kim Skak Larsen)
Newsgroups: comp.theory
Subject: Horn clauses
Message-ID: <4500@daimi.dk>
Date: 5 Jan 90 13:35:13 GMT
Sender: news@slyrf.dkuug.dk
Reply-To: kimskak@daimi.dk (Kim Skak Larsen)
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Lines: 18


How difficult is resolution of propositional Horn clauses,
i.e. consider a prolog program without variables that looks
something like
                    a :- b,c.
                    b :- c.
                    c.

and not like
                    a(X,Y) :- b(X),c(X,Y).
                    etc...

What is the complexity of answering queries such as 

                    a?

I heard a rumour about a result by Mike Paterson of O(n^2). 
Any references?