commit 1aff2d3c71300de11b511d7248a04fc3f45e2e9c
parent 935fcf3039fbec59cd9157870c966d4fd8323584
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 22 Aug 2025 14:44:15 +0200
commit with codex
Diffstat:
1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/post_correspondence_problem b/post_correspondence_problem
@@ -5,8 +5,12 @@ https://en.wikipedia.org/wiki/Post_correspondence_problem
The [computational_problem], given a set of [word] [pairs] (u_1, v_1), ..., (u_k, v_k), of deciding whether there is a sequence of indices i_1, ..., i_n in {1, ..., k} (potentially with repetitions) so that the concatenations
u_{i_1} ... u_{i_n} and v_{i_1} ... v_{i_n} are the same [word]
-It is an [undecidable] problem
+It is an [undecidable] problem, because it can encode a [Turing_machine]
+
+The bounded version is [NP_hard] for the same reason
Up: [computational_problem]
Aliases: PCP
+
+See also: [tiling_problem]
