Re: deductive databases

From: Mitch Harris <harrisq_at_tcs.inf.tu-dresden.de>
Date: Fri, 13 May 2005 10:21:22 +0200
Message-ID: <3ej6c2F3e3utU1@news.dfncis.de>

Jan Hidders wrote:

> I think there are. It is known that on an ordered domain FO(TC) (first
> order logic plus transitive closure) can express exactly all NSPACE[log
> n] queries and FO(LFP) (first order logic plus a least fixpoint
> operator) exactly all PTIME queries. The latter class is known to be
> strictly greater than the first.

P (det poly time) certainly includes NL (nondet log space) but I don't think it is currently known whether this inclusion is strict. Do you have a reference? (I'm looking at Immerman, Descriptive Complexity, 1999):

"It has not yet been proved that L is not equal to PH.."

where L is contained in NL, and P is contained in PH.

Maybe it has something to do with "ordered domain"?

-- 
Mitch Harris
(remove q to reply)

Received on Fri May 13 2005 - 03:21:22 CDT