Yes, for example TMSAT (Turing Machine SAT): TMSAT = {$ \lt \alpha, x, 1^n, 1^t \gt : \exists u \in$ $\{0,1\}^m$ such that $M_\alpha$ outputs 1 on input <$x,u$> within $t$ steps.} (Theorem 2.9 of Arora-Barak. See Chapter 2 draft: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#np) It is quite easy to show that this problem is NP-complete!