The Infinite Versions of LogSpace!=P Are Consistent with the Axioms of Set Theory.

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101898
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:17 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR2000-06.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101898, version 1

Collections

Citation

Grégory Lafitte, Jacques Mazoyer. The Infinite Versions of LogSpace!=P Are Consistent with the Axioms of Set Theory.. [Research Report] LIP RR-2000-06, Laboratoire de l'informatique du parallélisme. 2000, 2+9p. ⟨hal-02101898⟩

Share

Metrics

Record views

5

Files downloads

21