# Why can't we just reduce from Bounded HALT to Bounded PCP?

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?

• I'm guessing in the PCP case $k$ is given in unary Commented Apr 3 at 4:34
• 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. Commented Apr 3 at 7:02
• 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. Commented Apr 3 at 10:54
• 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...) Commented Apr 4 at 10:22