Home > Term: Post's correspondence problem (PCP)
Post's correspondence problem (PCP)
Given a set of pairs of strings, find a sequence of pairs such that the concatenation of all first members of the pairs is the same string as the concatenation of all second members. This is an undecidable problem.
- Part of Speech: noun
- Industry/Domain: Computer science
- Category: Algorithms & data structures
- Government Agency: NIST
0
Creator
- GeorgeV
-
(Gold) 1123 points - 100% positive feedback
