Emil Leon Post (né le 11 février 1897, mort le 21 avril 1954) était un mathématicien américain né sur le territoire de l'actuelle Pologne dans une famille juive. Il est à l'origine du problème de correspondance de Post.
Il a également publié en 1921 une étude exhaustive des clones des algèbres à deux éléments.
On part de deux suites finies U et V contenant le même nombre de mots finis sur un alphabet quelconque. Par exemple u1 = aba,u2 = b,u3 = a,u4 = a**b,v1 = a,v2 = b,v3 = ababa,v4 = b.
On cherche une suite d'indices i1,i2,...in telle que la concaténation des corresponde à celle des . Ici la suite (1,2,3,2,1) est une solution puisque u1u2u3u2u1 = v1v2v3v2v1 = ababababa.
Le problème de correspondance de Post (en abrégé PCP) consiste à déterminer l'existence d'une telle suite. Il est indécidable en général : il ne peut pas exister d'algorithme capable de fournir une réponse pour des U et V arbitraires.