post_correspondence_problem (579B)
1 # Post correspondence problem 2 3 https://en.wikipedia.org/wiki/Post_correspondence_problem 4 5 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 6 u_{i_1} ... u_{i_n} and v_{i_1} ... v_{i_n} are the same [word] 7 8 It is an [undecidable] problem, because it can encode a [Turing_machine] 9 10 The bounded version is [NP_hard] for the same reason 11 12 Up: [computational_problem] 13 14 Aliases: PCP 15 16 See also: [tiling_problem]