5
$\begingroup$

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.

$\endgroup$
14
  • 3
    $\begingroup$ From the G&J, [SR11] Bounded PCP: "... Reference: Constable, Hunt, and Sahni, 1974, "On the computational complexity of scheme equivalence". Generic transformation ...". See also the answer of a similar question on CS.stackexchange $\endgroup$ Sep 5, 2012 at 23:05
  • 1
    $\begingroup$ @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 $\endgroup$
    – vzn
    Sep 6, 2012 at 14:58
  • 2
    $\begingroup$ @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) $\endgroup$ Sep 6, 2012 at 17:41
  • 1
    $\begingroup$ @vzn: now at home I looked at the G&J, +1 to my memory :-) $\endgroup$ Sep 6, 2012 at 18:31
  • 1
    $\begingroup$ assafisr has no comment on what he means but imho "bounded" can be ambiguous. here is an example "BPCP" reduction to SAT 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 where the unlimited bound is taken as # of concatenated blocks. $\endgroup$
    – vzn
    Sep 6, 2012 at 18:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.