In "The Complexity of Enumeration and Reliability Problems", 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$?
  • $\begingroup$ The machine can convert the unary input to binary, and work on it (the input length changes from $|x|$ to $\log |x|$). $\endgroup$ – Marzio De Biasi Mar 31 '14 at 8:23
  • $\begingroup$ 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. $\endgroup$ – András Salamon Mar 31 '14 at 17:18

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.