title: Bounded PCP NP-Complete Proof
body: <p>I'm looking for a simple proof that shows that the <a href="https://en.wikipedia.org/wiki/Post_correspondence_problem" rel="nofollow">Bounded-PCP</a> 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.</p>
  
  <p>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?</p>
  
  <p>Thanks.</p>