The Infinite Versions of LogSpace!=P Are Consistent with the Axioms of Set Theory. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

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

(1) , (1)
1

Résumé

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.
Nous considérons les versions infinies des questions usuelles de complexité LogSpace?=P, NLogSpace?=P en étudiant, sur les structures infinies partiellement ordonnées, la comparaison de leurs logiques, les décrivants, au lieu de se limiter aux structures finies. Nous montrons que les versions infinies de ces fameuses questions de séparation sont consistantes avec la théorie des ensemble et nous donnons une condition suffisante sur les classes de complexité comparées pour obtenir les mêmes résultats avec d'autres classes de complexité.
Fichier principal
Vignette du fichier
RR2000-06.pdf (312.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101898 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101898 , version 1

Citer

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⟩
10 Consultations
110 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More