We know that:

  1. PCP is famously undecidable (as it can encode any DTM), but

  2. Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and

  3. Bounded-PCP (there is a matching sequence with at most k tiles) is NP-complete

Now, because P = NP would imply that Bounded-PCP is in P, wouldn't a P-time reduction from Bounded-HALT to Bounded-PCP prove P != NP by contradiction?

And if this is the case, what does actually go wrong in the following "naive reduction sketch"?

Given some DTM M and maximal number of steps k, w.l.o.g. assume a bounded tape of size 2k+1 (the TM cannot reach cells outside radius k).

Encode the DTM and its input as a PCP tile set using mostly the "standard construction" (e.g. as described here), but modify the encoding in such a way that the initial TM configuration is written out with all 2k+1 cells (i.e., the whole reachable bounded tape).

Each domino either copies a single tape cell, marks a configuration border, represents a state transition (around the TM head), or ensures the "cleanup" after a halting state was reached.

Careful analysis of the PCP encoding should allow to relate the number of steps the TM M is running on input x with the exact number of tiles in a matching domino sequence, i.e. (M,x,k) is an instance of Bounded-HALT iff for the tileset T and some sequence length k', (T, k') is an instance of Bounded-PCP, where k' = f(k) for some small function f.

Now do I too lazily gloss over something critical in the PCP encoding that probably will not work the way I would like it to, or did I miss something more subtle or fundamental concerning encodings of the instances? At least from what I understand, the step/tile number k should be coded in binary in both cases, etc.? Or does the blown-up "initial PCP tile" make an issue somehow?

  • 3
    $\begingroup$ I'm guessing in the PCP case $k$ is given in unary $\endgroup$ Commented Apr 3 at 4:34
  • 4
    $\begingroup$ I haven't looked at the details but I agree with @CommandMaster. Reading the question, I found it surprising to see Bounded-HALT mentioned as EXP-complete, because to me it is the prototypical example of a P-complete problem, as the bound $k$ is usually given in unary. So I think that the "paradox" results from a mismatch in how the bound $k$ is encoded in Bounded-HALT vs. Bounded-PCP. Once the mismatch is fixed, unary encoding gives P vs. NP, binary gives EXP vs. NEXP. In both cases, the existence of a Karp reduction from Bounded-HALT to Bounded-PCP is trivial. $\endgroup$ Commented Apr 3 at 7:02
  • 1
    $\begingroup$ I’m pretty sure your argument does not actually use that $M$ is deterministic. Thus, if correct, it would outright prove a contradiction (NP = NEXP) rather than just NP = EXP. But anyway, I agree with the comments above that most likely the NP-complete version of Bounded-PCP has $k$ in unary, whereas the EXP-complete version of Bounded-HALT has $k$ in binary. $\endgroup$ Commented Apr 3 at 10:54
  • $\begingroup$ Ok thanks, that makes sense / confirms my suspicion! There are so many variations of any such problem, I guess I mixed something up concerning the known results (and number encoding is a common culprit to hide exponential difference in representation...) $\endgroup$
    – apirogov
    Commented Apr 4 at 10:22


Your Answer

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