Consider two PCP instances over {0, 1}, each with lists A and B of three strings. X: A = (1, 10111, 10), B = (111, 10, 0). Y: A = (10, 011, 101), B = (101, 11, 011). Which is true?

1. AOnly PCP in X has a solution
2. BOnly PCP in Y has a solution
3. CPCP in both X and Y has a solution
4. DPCP in neither X nor Y has a solution

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. Only PCP in X has a solution

Explanation

X has the solution 2, 1, 1, 3: A gives 10111·1·1·10 = 1011111110 and B gives 10·111·111·0 = 1011111110. In Y every match must start with pair 1 (10/101), after which B stays one symbol ahead with no pair that closes the gap, so Y has no solution.