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$
  • 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$ – Marzio De Biasi Sep 5 '12 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 '12 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$ – Marzio De Biasi Sep 6 '12 at 17:41
  • 1
    $\begingroup$ @vzn: now at home I looked at the G&J, +1 to my memory :-) $\endgroup$ – Marzio De Biasi Sep 6 '12 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 '12 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.