Hey everyone, hope you're having a great day. Here's a question about the famous post correspondence problem This problem is undecidable according to Wiki Pedia, which means there are no algorithms to solve the problem. but can't we simply try all possible permutations of the dominos? what am I misunderstanding?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 10:54:16 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by MOOONI (previous revision, new revision, compare).
Auto comment: topic has been updated by MOOONI (previous revision, new revision, compare).
If you try all possible permutations, you would still have no guarantee of finding a solution because it is possible for the PCP to have no solution
My understanding is that the main issue is that the length of the answer can be arbitrarily large. This is because you're not just permuting the two lists of dominos -- you are actually allowed to repeat dominos as much as you like.
As the other commenter said, there can be no solution. So the naive algorithm of iterating over the length of the answer and trying all solutions of that length might never halt, because you never know if the solution is just really long or if none exist.
What makes the PCP problem undecidable is precisely the unlimited number of times a given tile can be used. If the number of tiles that could be used was bounded, your solution would indeed decide the problem. However, since you have an unlimited supply of tiles, you would have to find and check “all permutations of an infinite set of tiles”, which doesn’t quite work.
If we could check whether or not a solution exists for a set of tiles, would the problem be decidable?