Generic Machine Simulation Problem (GMSP)

Input

A string $x$, a description $M$ of a Turing machine $M$, and an integer $t$ coded in unary. (To be precise, the input is the string $x\#\overline{M}\#^t$, where $\#$ is a delimiter character not otherwise present in the string.)

Problem

Does $M$ accept $x$ within $t$ steps?

Status

$\P$-complete (Greenlaw, Hoover and Ruzzo [3, Theorem 4.1.2]).

Remarks

Buss and Goldsmith show a variant of this problem is complete with respect to quasilinear time reductions for $\mathsf{N^mP_l}$, a subclass of $\P$. See [1] for the appropriate definitions. They also show variants of TopCVP and CFGempty are complete in this setting.