Show how in Example $14\mathrm{.}6$ the checking of the trial solution can be done in

O$($n$2$logn$)$ time.

EXAMPLE $14\mathrm{.}6$

Reconsider the SAT problem. We made some rudimentary argument

to claim that this problem can be solved efficiently by a nondeterministic

Turing machine and, rather inefficiently, by a brute$-$force

exponential search. A number of minor points were ignored in that

argument.

Suppose that a CNF expression has length n$,$ with m different

literals. Since clearly m $<$ n$,$ we can take n as the problem size. Next,

we must encode the CNF expression as a string for a Turing machine.

We can do this, for example, by taking $=\{$x$,,,(,),,0,1\}$ and

encoding the subscript of x as a binary number. In this system, the

CNF expression $($x$1$ x$2)($x$3$ x$4)$ is encoded as

$($x$1$ x $10)($x$11$ x$100).$

Since the subscript cannot be larger than m$,$ the maximum length of

any subscript is log$2$m$.$ As a consequence the maximum encoded length

of an n$-$symbol CNF is O$($nlogn$).$ The next step is to generate a trial solution for the variables. Nondeterministically, this can be done in O$($n$)$ time. $($See Exercise $1$ at the end of this section.$)$ This trial solution is then substituted into the input string. This can be done in O$($n$2$logn$)$ time$.$ The entire process therefore can be done in O$($n$2$logn$)$ or O$($n$3)$ time, and SAT in NP$.$