<p>We know that:</p>
<ol>
<li><p>PCP is famously undecidable (as it can encode any DTM), but</p>
</li>
<li><p>Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and</p>
</li>
<li><p>Bounded-PCP (there is a matching sequence with at most k tiles) is NP-complete</p>
</li>
</ol>
<p><strong>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?</strong></p>
<p><em>And if this is the case, what does actually go wrong in the following &quot;naive reduction sketch&quot;?</em></p>
<hr />
<p>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).</p>
<p>Encode the DTM and its input as a PCP tile set using mostly the &quot;standard construction&quot;
(e.g. as described <a href="https://www.andrew.cmu.edu/user/ko/pdfs/lecture-17.pdf" rel="nofollow noreferrer">here</a>),
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).</p>
<p>Each domino either copies a single tape cell, marks a configuration border, represents a
state transition (around the TM head), or ensures the &quot;cleanup&quot; after a halting state was
reached.</p>
<p>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.</p>
<hr />
<p>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 &quot;initial PCP tile&quot; make an issue somehow?</p>

CC BY-SA 4.0
2024-04-03T04:34:54.323Z
I'm guessing in the PCP case $k$ is given in unary
Command Master
CC BY-SA 4.0
2024-04-03T07:02:05.373Z
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.
Damiano Mazza
CC BY-SA 4.0
2024-04-03T10:54:44.707Z
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.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T10:22:02.880Z
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...)
apirogov
<cc.complexity-theory><complexity-classes><time-complexity>
Why can't we just reduce from Bounded HALT to Bounded PCP?
apirogov
# Why can't we just reduce from Bounded HALT to Bounded PCP?

(Asked by: username_0 on 2024-04-02)

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](https://www.andrew.cmu.edu/user/ko/pdfs/lecture-17.pdf)),
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?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity

> **Comments:**
> **username_1**: I'm guessing in the PCP case $k$ is given in unary  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: 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...)  

---

## 0 answers

