Re: How to derive a consistent set of FOL constraints

On 6 Mar 2007, at 08:31, John F. Sowa wrote:

> To continue my point that efficiency *always* depends
> on what you're trying to do, I would like to address the
> problem of finding a consistent set of constraints:
>
> > I, as usual, recommend the
> > description logic complexity navigator:
> >    http://www.cs.man.ac.uk/~ezolin/logic/complexity.html
>
> Given a set of arbitrary first-order constraints, the problem
> of proving consistency is NP complete.

Well, it seems to me:
1) the problem of checking consistency (i.e., finding the existence  
of a model) of an arbitrary FOL formula is not decidable;
2) the problem of checking that a FOL formula is true in an  
interpretation (i.e., that a DB is consistent wrt a set of FOL  
constraints) is PSPACE-complete in *combined* complexity (i.e, wrt  
the size of the constraints and the DB), while it is in PTIME in  
*data* complexity (i.e., wrt the size of the DB only);
3) according to the abovementioned DL complexity navigator, the  
problem of checking consistency of DL KBs is most of the time decidable.

cheers
--e.