commit e6809d435306eaef0dfed7423590cfba0b3661a0
parent 4b979b893349ac352a545b466b3d784a889fa23e
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]
