Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!dino!ux1.cso.uiuc.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: Re: Horn clauses
Message-ID: <1799@uwm.edu>
Date: 6 Jan 90 00:57:46 GMT
References: <4500@daimi.dk>
Sender: news@uwm.edu
Reply-To: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 33

In article <4500@daimi.dk> kimskak@daimi.dk (Kim Skak Larsen) writes:
>
>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.
>
...
>What is the complexity of answering queries such as 
>
>                    a?

Your example:

		a :- b, c.  b :- c.  c.  :- a.

is actually a disguised version of this:

* Given the grammar:
*    Start symbol: *start
*    Nonterminals: a, b, c
*    Terminals: *c
*    Productions:
* 	  *start -> a
* 	  a -> b c
* 	  b -> c
* 	  c -> *c
* 
* Prove that the corresponding language is non-empty.

I think the corresponding general problem is NP-complete.