I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial time.

Here is my confusion. All Turing machine have a finite input alphabet $\Sigma$. Thus, none of them can solve any SAT problem with, say, $|\Sigma|+1$ variables. Thus, do we need another Turing machine with a larger input alphabet and its associated language to cover this problem? By induction, does this make SAT a union of an infinite number of languages?

If SAT is indeed a union of languages, and any Turing machine only responsible for solving boolean satisfiability problems with variables within its input alphabet, a Turing machine can simply "memorize" all possible 3-SAT problems without redundant clauses over this finite set of variables, and regurgitate the answer in linear time?

In other words, is there a loophole in the definintion of NP that allows for solving SAT by looking up pre-prepared answers? If such cheating is allowed, P=NP?


1 Answer 1


The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turing machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th symbol turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).

Note. The way a machine encodes the input can have a big effect on its time and place complexity note the adjacency lists and adjacency matrices representations of graphs.

  • 1
    $\begingroup$ I see, thank you so much! $\endgroup$
    – Hui Wang
    Dec 23, 2019 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.