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.
Received on Fri May 13 2005 - 14:40:24 CDT
