Skip to main content
MathOverflow

Return to Answer

small typo, math cleanup
Source Link
Emil
Emil
  • 726
  • 4
  • 13

Yes, for example TMSAT (Turing Machine SAT):

TMSAT = {$ \lt \alpha, x, 1^n, 1^t \gt : \exists u \in$ $\{0,1\}^m$$\{ \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$$\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!

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 $\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!

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!

fixed angle brackets
Source Link
Peter Shor
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

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$$\langle x$,$u$>$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!

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!

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 $\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!

added 2 characters in body
Source Link
Emil
Emil
  • 726
  • 4
  • 13

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$$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!

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!

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!

Source Link
Emil
Emil
  • 726
  • 4
  • 13