From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: "the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (encodings over (0,1)) of such machines provides an indexing of 𝑃𝑇𝐼𝑀𝐸...we have Theorem: No universal simulator for this indexing can run in 𝑃𝑆𝑃𝐴𝐢𝐸."

He then goes on to say: "can it be proved that π‘”π‘Ÿπ‘ˆ for any indexing of 𝑃𝑇𝐼𝑀𝐸 requires more than 𝑃𝑆𝑃𝐴𝐢𝐸 to compute? We have proved this for a wide class of indexings, namely counter indexings satisfying the succinct composition property."

I'm wondering what causes simulation of the enumerated machines to be difficult, and can it be circumvented--namely: does there exist an enumeration of machines for all languages in $𝑃$ that describes the machines in such a way that allows the machines, as specified, to be simulated efficiently by a simulator (with no more than 𝑃𝑇𝐼𝑀𝐸 overhead) on any input--or (basically) as Kozen puts it "allow(s) easy construction of programs from (their) specification"?

Looking for any progress that has been made since Kozen asked ^ the above question ^.

  • 3
    $\begingroup$ You seem to be confused by basic terminology. The reason that the simulator does not run in P, or even in PSPACE, has nothing to do with β€œinefficiency” of the simulation. I don’t know how exactly Kozen defines β€œTuring machines with polynomial time counters”, but basically, it amounts to the following: the input of the simulator is a triple $(M,k,x)$, where $M$ is a description of the simulated Turing machine, $k$ is a time-bound exponent, and $x$ is the simulated input. The simulator runs $M$ on input $x$ for at most $|x|^k$ steps, and outputs either the output of the simulated TM, or, ... $\endgroup$ Jun 24 '20 at 13:50
  • 3
    $\begingroup$ ... say, NO, if the time bound is exhausted. This simulation needs time $|x|^k$ times some small overhead, and may likewise use space $|x|^k$ times some small overhead. For simulation of any specific TM, $M$ and $k$ are constants, hence this is polynomial time, and the time and space used is really the time and space needed by $M$ with a small overhead. However, in terms of the input of the simulator, the bound is exponential, as $|x|^k$ is exponential in $k$. Thus, the simulator runs in exponential time and space. $\endgroup$ Jun 24 '20 at 13:54
  • 2
    $\begingroup$ In order for a simulator to run in PSPACE, you would need to be able, given $(M,k,x)$, to simulate machine $M$ on input $x$ for $|x|^k$ steps using space only $(|M|+|x|+k)^c$ for some universal constant $c$. $\endgroup$ Jun 24 '20 at 13:59
  • 2
    $\begingroup$ No, because it contradicts the time hierarchy theorem, I already told you. If the simulator runs in time $n^c$, it cannot simulate languages in $\mathrm{DTIME}(n^{c+1})\smallsetminus\mathrm{DTIME}(n^c)$. $\endgroup$ Jun 24 '20 at 14:01
  • 2
    $\begingroup$ Whether $\mathrm{P\subseteq NTIME}(n^c)$ for some constant $c$ is an open problem, but as far as I am aware, the expected answer is the same, namely $\mathrm{DTIME}(n^{c+1})\nsubseteq\mathrm{NTIME}(n^c)$. $\endgroup$ Jun 24 '20 at 14:06

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.