Skip to main content
4 of 4
small typo, math cleanup
Emil
  • 726
  • 4
  • 13

Yes, for example TMSAT (Turing Machine SAT):

TMSAT = $\{ \langle \alpha, x, 1^n, 1^t \rangle : \exists u \in \{0,1\}^n$ such that $M_\alpha$ outputs 1 on input $\langle x,u \rangle$ 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!

Emil
  • 726
  • 4
  • 13