<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>

CC BY-SA 3.0
2012-09-05T22:31:43.697Z
Have you checked Garey and Johnson's "Computers and Intractability: A Guide to the Theory of NP-Completeness"?
Kaveh
CC BY-SA 3.0
2012-09-05T22:36:51.277Z
Yes, there's nothing but a definition there and a reference I couldn't find. Any idea?
assafisr
CC BY-SA 3.0
2012-09-05T23:05:43.570Z
From the G&J, [SR11] Bounded PCP: "... *Reference*: [Constable, Hunt, and Sahni, 1974, "On the computational complexity of scheme equivalence"](http://dspace.library.cornell.edu/bitstream/1813/6041/1/74-201.pdf). Generic transformation ...". See also the [answer of a similar question on CS.stackexchange](http://cs.stackexchange.com/questions/2783/a-polynomial-reduction-from-any-np-complete-problem-to-bounded-pcp)
Marzio De Biasi
CC BY-SA 3.0
2012-09-06T03:46:03.080Z
assafisr, think you have good point and have zoomed onto a key subtlety. this is not totally as simple as it looks or as handled in the cs.SE answers—think because the bound has to be _polynomial_ & those answers dont seem to take that into account. so the _polynomially bounded_ PCP problem is NP complete, but if the bound in length is specified in binary with no other limit, this appears to me to be NExpSpace complete! basically the PCP defines a computational tableau (concatenated TM IDs/Instantaneous Descriptions) of the problem bounded by the specified length.
vzn
CC BY-SA 3.0
2012-09-06T07:21:59.123Z
@vzn: why do you say "don't seem to take that into account?" In the Raphael's answer it is written: "... so the constructed BPCP instance  has polynomial size. Furthermore, the construction of every tile is clearly possible in polynomial time ..."; the same attention is found in the standard reduction from TM.
Marzio De Biasi
CC BY-SA 3.0
2012-09-06T14:58:24.333Z
@marzio both answers seem to prove its NP Hard assuming a polynomial bound, but maybe not NP Complete which requires the assumption/restriction of a polynomial bound on the size of the PCP. its also a subtlety in some problems where it is not always clear if some parameter is fixed across all instances or given as an input to the problem. if the bound is an input to the problem, think assafisrs & my comments stand
vzn
CC BY-SA 3.0
2012-09-06T15:15:14.903Z
@vzn: but both answers use the $k$ bound of the BPCP (which is less than or equal the number of tiles): 1) "... so k corresponds to the BPCP's bound: if we can solve this PCP with <= k tiles ..."; 2) "... then ask whether there is a solution that uses f(p(n)) dominoes, where f is some polynomial function that expresses the number of dominoes necessary for the solution to exist ..."
Marzio De Biasi
CC BY-SA 3.0
2012-09-06T17:22:55.487Z
@marzio where does length bound $k$ on the PCP length come from? the input, as assafisr is asking? skimmed the Constable/Hunt/Sahni 1974 paper, its long 73pgs, can anyone point to the right section? it seems to have zero ref to PCPs by that name
vzn
CC BY-SA 3.0
2012-09-06T17:41:56.557Z
@vzn: I don't have the G&J here however the bounded PCP problem (we are talking about BOUNDED PCP) should be: *Instance:* given two list of strings $u_i,...,u_n$ and $w_1,...w_n$ from $\Sigma^*$, and a $K \leq n$. *Question:* is there a sequence of $k \leq K$ integers (not necessarily distinct) between 1 and n such that $u_{i_1} ... u_{i_k} = w_{i_1}...w_{i_k}$ ? So every valid solution has length less than or equal to the number of "tiles" (and thus verifiable in linear time)
Marzio De Biasi
CC BY-SA 3.0
2012-09-06T18:07:21.780Z
@marzio $K \leq n$?! that does not seem to be a constraint on the wikipedia pg describing the BPCP variant at end. thought the "bound" was on the # of "blocks" in the solution and arbitrary $K$ specified on input. thought assafirs 2nd sentence above was describing that. there is more than one way to bound it. maybe there is some ref somewhere that makes this clear.
vzn
CC BY-SA 3.0
2012-09-06T18:31:49.513Z
@vzn: now at home I looked at the G&J, +1 to my memory :-)
Marzio De Biasi
CC BY-SA 3.0
2012-09-06T18:55:56.920Z
assafisr has no comment on what he means but imho "bounded" can be ambiguous. here is an example "BPCP" [reduction to SAT](http://cs.nyu.edu/courses/fall05/V22.0480-001/post2Sat.html) but it has the same issue, it doesnt bound the length (it doesnt claim its an NP completeness proof). here is another case of a [ref to BPCP code](http://code.google.com/p/post-correspondence-brute/) where the unlimited bound is taken as # of concatenated blocks.
vzn
CC BY-SA 3.0
2012-09-06T19:49:30.920Z
@vzn understood me right - The N boundary is part of the problem's input and it is not fixed or bounded in any way.
This fact makes it even harder to understand the verifying algorithm's complexity in relation to the size of X and Y arrays.
Thanks for the reduction, I will read it.
assafisr
CC BY-SA 3.0
2012-09-06T21:39:42.857Z
fyi looking at the typical proof for PCP that shows its Turing completeness & conversion of a TM to it might help understanding. see eg Hopcroft & Ullman 1979, or as cited in "Using DNA to solve the BPCP" by Kari, Gloor, Yu: Hopcroft & Ullman, _Formal Languages & their Relation to Automata_, Addison Wesley, 1969. would still like contrasting ref that showed what might instead be called the "finite PCP" with finite block concatenation length specified as binary on input is NExpSpace complete, but maybe its too basic for anyone to remark on that
vzn
<cc.complexity-theory><np-hardness><post-correspondence>
Bounded Post Correspondence Problem NP-Complete Proof
assafisr
# Bounded Post Correspondence Problem NP-Complete Proof

(Asked by: username_0 on 2012-09-05)

I'm looking for a simple proof that shows that the [Bounded-PCP](https://en.wikipedia.org/wiki/Post_correspondence_problem) 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.

**Tags:** cc.complexity-theory, np-hardness, post-correspondence

> **Comments:**
> **username_1**: Have you checked Garey and Johnson's "Computers and Intractability: A Guide to the Theory of NP-Completeness"?  
> **username_0**: Yes, there's nothing but a definition there and a reference I couldn't find. Any idea?  
> **username_2**: From the G&J, [SR11] Bounded PCP: "... *Reference*: [Constable, Hunt, and Sahni, 1974, "On the computational complexity of scheme equivalence"](http://dspace.library.cornell.edu/bitstream/1813/6041/1/74-201.pdf). Generic transformation ...". See also the [answer of a similar question on CS.stackexchange](http://cs.stackexchange.com/questions/2783/a-polynomial-reduction-from-any-np-complete-problem-to-bounded-pcp)  
> **username_3**: username_0, think you have good point and have zoomed onto a key subtlety. this is not totally as simple as it looks or as handled in the cs.SE answers—think because the bound has to be _polynomial_ & those answers dont seem to take that into account. so the _polynomially bounded_ PCP problem is NP complete, but if the bound in length is specified in binary with no other limit, this appears to me to be NExpSpace complete! basically the PCP defines a computational tableau (concatenated TM IDs/Instantaneous Descriptions) of the problem bounded by the specified length.  
> **username_2**: @username_3: why do you say "don't seem to take that into account?" In the Raphael's answer it is written: "... so the constructed BPCP instance  has polynomial size. Furthermore, the construction of every tile is clearly possible in polynomial time ..."; the same attention is found in the standard reduction from TM.  
> **username_3**: @marzio both answers seem to prove its NP Hard assuming a polynomial bound, but maybe not NP Complete which requires the assumption/restriction of a polynomial bound on the size of the PCP. its also a subtlety in some problems where it is not always clear if some parameter is fixed across all instances or given as an input to the problem. if the bound is an input to the problem, think username_0s & my comments stand  
> **username_2**: @username_3: but both answers use the $k$ bound of the BPCP (which is less than or equal the number of tiles): 1) "... so k corresponds to the BPCP's bound: if we can solve this PCP with <= k tiles ..."; 2) "... then ask whether there is a solution that uses f(p(n)) dominoes, where f is some polynomial function that expresses the number of dominoes necessary for the solution to exist ..."  
> **username_3**: @marzio where does length bound $k$ on the PCP length come from? the input, as username_0 is asking? skimmed the Constable/Hunt/Sahni 1974 paper, its long 73pgs, can anyone point to the right section? it seems to have zero ref to PCPs by that name  
> **username_2**: @username_3: I don't have the G&J here however the bounded PCP problem (we are talking about BOUNDED PCP) should be: *Instance:* given two list of strings $u_i,...,u_n$ and $w_1,...w_n$ from $\Sigma^*$, and a $K \leq n$. *Question:* is there a sequence of $k \leq K$ integers (not necessarily distinct) between 1 and n such that $u_{i_1} ... u_{i_k} = w_{i_1}...w_{i_k}$ ? So every valid solution has length less than or equal to the number of "tiles" (and thus verifiable in linear time)  
> **username_3**: @marzio $K \leq n$?! that does not seem to be a constraint on the wikipedia pg describing the BPCP variant at end. thought the "bound" was on the # of "blocks" in the solution and arbitrary $K$ specified on input. thought assafirs 2nd sentence above was describing that. there is more than one way to bound it. maybe there is some ref somewhere that makes this clear.  
> **username_2**: @username_3: now at home I looked at the G&J, +1 to my memory :-)  
> **username_3**: username_0 has no comment on what he means but imho "bounded" can be ambiguous. here is an example "BPCP" [reduction to SAT](http://cs.nyu.edu/courses/fall05/V22.0480-001/post2Sat.html) but it has the same issue, it doesnt bound the length (it doesnt claim its an NP completeness proof). here is another case of a [ref to BPCP code](http://code.google.com/p/post-correspondence-brute/) where the unlimited bound is taken as # of concatenated blocks.  
> **username_0**: @username_3 understood me right - The N boundary is part of the problem's input and it is not fixed or bounded in any way. This fact makes it even harder to understand the verifying algorithm's complexity in relation to the size of X and Y arrays. Thanks for the reduction, I will read it.  
> **username_3**: fyi looking at the typical proof for PCP that shows its Turing completeness & conversion of a TM to it might help understanding. see eg Hopcroft & Ullman 1979, or as cited in "Using DNA to solve the BPCP" by Kari, Gloor, Yu: Hopcroft & Ullman, _Formal Languages & their Relation to Automata_, Addison Wesley, 1969. would still like contrasting ref that showed what might instead be called the "finite PCP" with finite block concatenation length specified as binary on input is NExpSpace complete, but maybe its too basic for anyone to remark on that  

---

## 0 answers

