Post correspondence problem
undecidable decision problem
Facts
7 properties- Instance of
- decision problem
- Defining formula
- \alpha _{i_1}\dotsm \alpha _{i_K}=\beta _{i_1}\dotsm \beta _{i_K}\qquad(\alpha_1,\dotsc,\alpha_N,\beta_1,\dotsc,\beta_N\in\Sigma^*)
- Different from
- phencyclidine[4]
- Discoverer or inventor
- Emil Leon Post[1]
- Named after
- Emil Leon Post[2]
- Time of discovery or invention
- 1946[3]
🏷️ Also known as
en Post correspondence problem
en Post's correspondence problem
cs Postův korespondenční problém
de Post correspondence problem
de Postsches Korrespondenzproblem
de Post'sches Korrespondenzproblem
de PCP
de PKP
es problema de correspondencia de Post
fa مسئله تناظر پست
fr Problème de correspondance de Post
he בעיית ההתאמה של פוסט
nl Correspondentieprobleem van Post
nl Post Correspondence Problem
pl Problem odpowiedniości Posta
pt Problema da correspondência de Post
tr Post Correspondence Problemi
uk Проблема збіжності Поста
zh 波斯特对应问题
🔖 Identifiers · 4
- Dictionary of Algorithms and Data Structures ID
- pcp
- Freebase ID
- /m/0h7t4
- Microsoft Academic ID (discontinued)
- 123609886
- PlanetMath ID
- PostCorrespondenceProblem
🔗 Connections
Computational complexity 1
Created notable works 1
Different from 1
Discoverer or inventor 1
Instance of 1
Maintained by WikiProject 1
Named after 1
Press Enter · cited answer in seconds