3
$\begingroup$

At page 277 of Sipser's Introduction to the Theory of Computation, a proof of the NP-completeness of SAT is given.

The following comment is made on the trace of some machine $N$ which can decide a language $A\in\mathrm{NP}$:

"Next, we take any language $A$ in NP and show that $A$ is polynomial time reducible to SAT. Let $N$ be a nondeterministic Turing machine that decides $A$ in $n^k$ time for some constant $k$. (For convenience, we actually assume that $N$ runs in time $n^k-3$, but only those readers interested in details should worry about this minor point.)" (p. 277)

Interestingly, Levin's paper, Universal Search Problems, which discusses the search version of computation (in contrast to the decision version) states:

"Two function $f (n)$ and $g (n)$ will be said to be equal if there exists some $k$ such that: \begin{equation} f (n) \leq (g (n) +2)^k\ \textrm{and} \ g (n) \leq (f (n) +2) ^k. \end{equation} The term less than or equal is defined similarly." (p.1 of the paper)

Levin is sometimes co-cited with Cook for the proof of the NP-completeness of SAT (Cook-Levin theorem).

So what are those $2$ and $3$ constants? Are they even related or was it just an intuition? In conventional big-O notation, we would have said $\pm O(1)$. But here, both authors take the time to specify an exact constant, and both are discussing the notion of polynomial-time reduction.

Improve this question
$\endgroup$
1
  • $\begingroup$ Presumably these constants pop out of the proof, but it's hard to tell without reading these particular proofs. They are not important anyhow, the entire idea of asymptotic notation is being able to ignore such details. $\endgroup$
    – Yuval Filmus
    Commented Jun 8, 2014 at 17:40

1 Answer 1

Reset to default
4
$\begingroup$

The tableau used in the proof has dimensions $n^k \times n^k$. The reason is that each row represents the contents of the tape, and the number of symbols on the tape cannot possibly be more than the runtime of the algorithm. However, in the proof, the first and last cell of each row is a # symbol, and each row also needs one cell to store the current state $q$ of the TM. Thus to be sure we are able to fit the entire contents of the tape and these 3 extra symbols in $n^k$ cells, we must say the runtime (and hence the space used on tape) is bounded by $n^k - 3$.

Improve this answer
$\endgroup$

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.