<p>In <a href="http://dx.doi.org/10.1137/0208032" rel="nofollow">"The Complexity of Enumeration and Reliability Problems"</a>, Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page 419, he writes:</p>

<blockquote>
  <p>it is sufficient to simulate just the following fixed TM, $M$, which
  is clearly complete for $\#P_1$: on unary input $n$, $M$ first
  verifies that ... and then simulates the $i$th machine in $\#TIME(n)$
  on input $j$ (or vice versa)</p>
</blockquote>

<p>I find the existence of such a machine surprising:</p>

<ul>
<li>Does there exist a machine complete for PTIME that can simulate any
other PTIME machine. That is, a PTIME machine that takes a number $i$ and a string $s$ as input, and then executes the $i$th PTIME machine
with input $s$? </li>
<li>Would the existence of such a machine not lead to a
contradiction, because it would have a complexity $O(n^k)$, which means that no PTIME machine can have complexity $O(n^{k+1})$.</li>
<li>If this is indeed not possible for PTIME, why is it possible for $\#P_1$?</li>
</ul>

CC BY-SA 3.0
2014-03-31T08:23:42.260Z
The machine can convert the unary input to binary, and work on it (the input length changes from $|x|$ to $\log |x|$).
Marzio De Biasi
CC BY-SA 3.0
2014-03-31T17:18:13.033Z
If some machine solves a PTIME-complete problem $Q$ in $O(n^k)$ time, that doesn't mean that every problem $Q'$ in PTIME is also in $DTIME[n^k]$: the reduction of $Q'$ to $Q$ generally increases the size of the instance.
András Salamon
<complexity-classes><counting-complexity><universal-computation>
Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?
guyvdb
# Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

(Asked by: username_0 on 2014-03-31)

In ["The Complexity of Enumeration and Reliability Problems"](http://dx.doi.org/10.1137/0208032), Valiant mentions the existence of a single Turing machine that is complete for the class $\#P\_1$ (i.e., $\#P$ with unary input). On page 419, he writes:

> it is sufficient to simulate just the following fixed TM, $M$, which
> is clearly complete for $\#P\_1$: on unary input $n$, $M$ first
> verifies that ... and then simulates the $i$th machine in $\#TIME(n)$
> on input $j$ (or vice versa)

I find the existence of such a machine surprising:

* Does there exist a machine complete for PTIME that can simulate any
  other PTIME machine. That is, a PTIME machine that takes a number $i$ and a string $s$ as input, and then executes the $i$th PTIME machine
  with input $s$?
* Would the existence of such a machine not lead to a
  contradiction, because it would have a complexity $O(n^k)$, which means that no PTIME machine can have complexity $O(n^{k+1})$.
* If this is indeed not possible for PTIME, why is it possible for $\#P\_1$?

**Tags:** complexity-classes, counting-complexity, universal-computation

> **Comments:**
> **username_1**: The machine can convert the unary input to binary, and work on it (the input length changes from $|x|$ to $\log |x|$).  
> **username_2**: If some machine solves a PTIME-complete problem $Q$ in $O(n^k)$ time, that doesn't mean that every problem $Q'$ in PTIME is also in $DTIME[n^k]$: the reduction of $Q'$ to $Q$ generally increases the size of the instance.  

---

## 0 answers

