Le Problème de correspondance de Emil Post (PCP) est un problème classique en informatique qui peut être énoncé comme suit : Étant donné deux morphismes g et h entre deux monoïdes libres A et B, est-ce décidable s’il existe un x non trivial dans A tel que g(x)=h(x) ? Cette question peut être formulée en termes d'égaliseurs, posée dans le contexte de groupes, et généralisée: si l'égaliseur de g et h est défini comme le sous-groupe constitué de tous les x où g(x)=h(x), il est naturel de se demander non seulement si l'égaliseur est trivial, mais quel peut être son rang ou sa base.

Alors que le PCP pour les monoïdes est notoirement insoluble et agit comme une source d'indécidabilité dans de nombreux domaines de l'informatique, le PCP pour les groupes libres est ouvert. Dans cet exposé je donnerai un aperçu de ce que l'on sait du PCP pour les groupes et montrerai que le PCP est indécidable dans les groupes hyperboliques (travail en collaboration avec Alex Levine et Alan Logan)