I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input configuration of pile $$(t_1/b_1, t_2/b_2,...t_n/b_n)$$ concatenating $t_1, t_2,...,t_n$ as a string $t$ and concatenating $b_1, b_2, ..., b_n$ as a string $b$, then compare $t$ and $b$ to see if the two are equal and then conclude that the input is actually a solution to PCP.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ a/ the bounded version/ variant of this problem is NP complete. see eg bounded PCP NP complete / Theoretical Computer Science $\endgroup$– vznNov 16, 2015 at 16:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The Post correspondence problem is undecidable, and in particular it is not in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just proved it). That is, for your certifier to prove that the Post correspondence problem is in NP, it needs to run in polynomial time (in terms of the size of the PCP instance). It turns out that in this case there isn't always a polynomial size solution even when the problem is solvable. In fact, there is no computable bound on the size of a potential solution, since otherwise the problem would be decidable!
answered Nov 16, 2015 at 6:18
$\begingroup$
$\endgroup$
Your witness is polynomial in the size of the solution not in the size of the input. You have no way of bounding the length of potential solutions. Your proof shows that PCP is recursively enumerable.
