Information Technology Reference
In-Depth Information
SERIAL COMPUTATIONAL MODELS
8.3 Given an instance of satisfiability, namely, a set of clauses over a set of literals and values
for the variables, show that the clauses can be evaluated in time quadratic in the length
of the instance.
8.4 Consider the RAM of Section
8.4.1
.Let
l
(
I
) be the length, measured in bits, of the
of the RAMs input registers. Similarly, let
l
(
v
) be the maximal length of any
integer addressed by an instruction in the RAMs program. Show that after
k
steps the
contents of any RAM memory location is at most
k
+
l
(
I
contents
)+
l
(
v
)
.
Given an example of a computation that produces a word of length
k
.
Hint:
Consider which instructions have the effect of increasing the length of an integer
used or produced by the RAM program.
8.5 Consider the RAM of Section
8.4.1
. Assume the RAM executes
T
steps. Describe a
Turing-machine simulation of this RAM that uses space proportional to
T
2
measured
in bits.
Hint:
Represent each RAM memory location visited during a computation by an
(
address
,
contents
)
pair. When a RAM location is updated, fill the cells on the
second tape containing the old
(
address
,
contents
)
pair with a special “blank” char-
acter and add the new
(
address
,
contents
)
pair to the end of the list of such pairs.
Use the results of Problem
8.4
to bound the length of individual words.
8.6 Consider the RAM of Section
8.4.1
. Using the result of Problem
8.5
, describe a multi-
tape Turing machine that simulates in
O
(
T
3
)
steps a
T
-step computation by the RAM.
Hint:
Let your machine have seven tapes: one to hold the input, a second to hold
the contents of RAM memory recorded as
(
address
,
contents
)
pairs separated and
terminated by appropriate markers, a third to hold the current value of the program
counter, a fourth to hold the memory address being sought, and three tapes for operands
and results. On the input tape place the program to be executed and the input on which
it is to be executed. Handle the second tape as suggested in Problem
8.5
.Whenper-
forming an operation that has two operands, place them on the fifth and sixth tapes
and the result on the seventh tape.
8.7 Justify using the number of tape cells as a measure of space for the Turing machine
when the more concrete measure of bits is used for the space measure for the RAM.
I
CLASSIFICATION OF DECISION PROBLEMS
8.8 Given a Turing machine, deterministic or not, show that there exists another Turing
machine with a larger tape alphabet that performs the same computation but in a num-
ber of steps and number of tape cells that are smaller by constant factors.
8.9 Show that strings in
TRAVELING SALESPERSON
can be accepted by a deterministic
Turing machine in an exponential number of steps.
COMPLEMENTS OF COMPLEXITY CLASSES
8.10 Show that
VALIDITY
islog-spacecompletefor
coNP
.
8.11 Prove that the complements of
NP
-complete problems are
coNP
-complete.
Search WWH ::
Custom Search