CSC 456/656 Boolean Satisfiability is NP-Complete
Date, November 26, 2002
We will use a slight variation of the definition of Turing Machine given on
page 319 of our textbook. As given in class, M will not be allowed to scan
to the left of the initial cell. That is, the tape is infinite to the right,
and has no cells to the left of the initial (leftmost) cell.
If M is a Turing Machine, an ID of M
is defined on page 320 of our textbook, but with an appropriate variation -
blank cells at the beginning of the tape are indicated by the symbol B.
For example, if the machine is scanning the second cell and is in state q,
and the first three cells contain blank, a, and b, then the ID is Baqb,
not aqb.
Padded IDs. For this problem, we shall assume that
all IDs are "padded" with a single $ at the beginning, and with enough
blanks to make them have a desired length. For example, the ID aqb,
if padded to have length 8, would be replaced by $aqbBBBB
Fix a Turing Machine M. Let Sigma be the input alphabet
of M. Let be an integer. We will describe a function that, for each
string w over Sigma, gives
a boolean expression eM,t,w which has the following properties:
-
There is a valid computation of M which accepts w in at most t steps
if and only if eM,t,w is satisfiable.
-
The length of the string eM,t,w is a
polynomial function of t. In fact, the length of
eM,t,w does not exceed some constant times mt2log t,
where m depends only on M.
-
For fixed M, the time required to construct
eM,t,w is a polynomial function of t.
Back to
Course Page