Re: Horn clauses

Article View: comp.theory

Article #1998

#1998

From: M. Alex Colvin
Date: Tue, 09 Jan 1990 14:25

5 lines
615 bytes

>How difficult is resolution of propositional Horn clauses,
>i.e. consider a prolog program without variables ...

isn't this the same as SAT (Boolean satisfiability), the canonical
NP-complete problem?

Technical Details

Message-ID: <813@ra.cs.Virginia.EDU>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!aplcen!haven!uvaarpa!ra!mac

References: <4500@daimi.dk> <1799@uwm.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!aplcen!haven!uvaarpa!ra!mac
From: mac@ra.cs.Virginia.EDU (M. Alex Colvin)
Newsgroups: comp.theory
Subject: Re: Horn clauses
Summary: satisfiability
Message-ID: <813@ra.cs.Virginia.EDU>
Date: 9 Jan 90 14:25:20 GMT
References: <4500@daimi.dk> <1799@uwm.edu>
Organization: U.Va. CS Department, Charlottesville, VA
Lines: 5

Reply to Parent Message