The exact complexity of the infinite Post Correspondence Problem - Logique
Article Dans Une Revue Information Processing Letters Année : 2015

The exact complexity of the infinite Post Correspondence Problem

Résumé

In this short note, we give the exact complexity of the infinite Post Correspondence Problem, showing that it is Π^0_1-complete. Surprisingly, it turns out that the infinite Post Correspondence Problem is not " more complex " than the Post Correspondence Problem, which is known to be Σ^0_1-complete, but has the exact dual complexity. This gives an answer to a question of Simonnet [Sim10].

Domaines

Logique [math.LO] Complexité [cs.CC] Théorie et langage formel [cs.FL] Logique en informatique [cs.LO]
Fichier principal
Vignette du fichier
Coomplexity-Infinite-PCP - IPL - revised - Version-2.pdf (83.6 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Olivier Finkel  : Connectez-vous pour contacter le contributeur

https://hal.science/hal-01376975

Soumis le : jeudi 6 octobre 2016-09:50:25

Dernière modification le : vendredi 3 mai 2024-14:05:43

Archivage à long terme le : samedi 7 janvier 2017-12:51:11

Télécharger pour visualiser

Dates et versions

hal-01376975 , version 1 (06-10-2016)

Identifiants

Citer

Olivier Finkel. The exact complexity of the infinite Post Correspondence Problem. Information Processing Letters, 2015, 115 (6-8), pp.609-611. ⟨10.1016/j.ipl.2015.02.009⟩. ⟨hal-01376975⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-PARIS7 UPMC CNRS ELM INSMI IMJ IMJ_LOG SORBONNE-UNIVERSITE SU-SCIENCES UP-SCIENCES
78 Consultations
573 Téléchargements

Altmetric

Partager

More