A complete language for $ \mathbf{EXPTIME}$

Definition 14   $ L = \{(N, 1^{\vert I\vert^k}, I)\mid N\textrm{ is an exp time machine that accepts }I\textrm{ in }2^{\vert I\vert^k}\textrm{ steps}\}$

Theorem 11   $ L$ is complete for $ \mathbf{EXPTIME}$.

Proof. $ \forall x \in \mathbf{EXPTIME}, x \leq L$. $ \exists$ Turing Machine $ M$ and a $ k$ such that $ M$ decides $ x$ in time $ 2^{n^k}$.

Polynomial $ x$: read $ I$, Decide if $ M$ accepts $ I$. Call program for $ L$ on input $ (M, 1^{\vert I\vert^k}, I)$. $ \qedsymbol$



bighead 2008-10-29