I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so.It is clear to me that the problem is decidable but I cannot find any reduction from an NP-Hard problem to this one.Moreover, the verifying algorithm might go through a series of N indexes which is exponential in comparison to the input size (N) which is logN, so how can this problem be in NP?Thanks.
Bounded Post Correspondence Problem NP-Complete Proof
cc.complexity theory;np hardness;post correspondence