Abstract of Paper

The Infinite Versions of LogSpace!=P Are Consistent with the Axioms of Set Theory
by Gregory Lafitte and Jacques Mazoyer


We consider the infinite versions of the usual computational complexity
questions LogSpace?=P, NLogSpace?=P by studying the comparison of their
descriptive logics on infinite partially ordered structures rather than
restricting ourselves to finite structures. We show that the infinite
versions of those famous class separation questions are consistent with the
axioms of set theory and we give a sufficient condition on the complexity
classes in order to get other such relative consistency results.