Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Fri, 13 May 2005 19:40:24 GMT
Message-ID: <Io7he.90037$g21.5412959_at_phobos.telenet-ops.be>
>
> 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"?
Date: Fri, 13 May 2005 19:40:24 GMT
Message-ID: <Io7he.90037$g21.5412959_at_phobos.telenet-ops.be>
Mitch Harris wrote:
> 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"?
I'm afraid it has to do with me being a bit "unordered". :-( The problem is indeed still open.
- Jan Hidders