Information Technology Reference
In-Depth Information
8.29 Give a proof that the
PARTITION
problem defined below is
NP
-complete.
PARTITION
Instance:
Aset
Q
=
{
a
1
,
a
2
,
...
,
a
n
}
of positive integers.
Answer:
“Yes” if there is a subset of
Q
that adds to
2
1
≤i≤n
a
i
.
PSPACE
-COMPLETE PROBLEMS
8.30 Show that the procedure
tree eval
described in the proof of Theorem
8.12.1
can
be modified slightly to apply to the evaluation of the trees generated in the proof of
Theorem
8.12.3
.
Hint:
A vertex of in-degree
k
can be replaced by a binary tree of
k
leaves and depth
log
2
k
.
THE CIRCUIT MODEL OF COMPUTATION
8.31 Prove that the class of circuits described in Section
3.1
that simulate a finite-state ma-
chine are uniform.
8.32 Generalize Theorems
8.13.1
and
8.13.2
to uniform circuit families and Turing ma-
chines that use more than logarithmic space and polynomial time, respectively.
8.33 Write a
O
(log
2
n
)
-space program based on the one in Fig.
8.20
to describe a circuit for
the transitive closure of an
n
×
n
matrix based on matrix squaring.
THE PARALLEL RANDOM-ACCESS MACHINE MODEL
8.34 Complete the proof of Lemma
8.14.2
by making specific assignments of data to mem-
ory locations. Also, provide formulas for the assignment of processors to tasks.
8.35 Give a definition of a
log-space uniform family of PRAMs
for which Lemma
8.14.1
can be extended to show that the function
f
:
B
∗
→B
∗
computed by a log-space fam-
ily of PRAMs can also be computed by a log-space uniform family of circuits satisfying
the conditions of Lemma
8.14.1
.
8.36 Exhibit a non-uniform family of PRAMs that can solve problems that are not recur-
sively enumerable.
8.37 Lemma
8.14.1
is stated for PRAMs in which the CPU does not access a common mem-
ory address larger than
O
(
p
(
n
)
t
(
n
))
. In particular, this model does not permit indirect
addressing. Show that this theorem can be extended to RAM CPUs that do allow
indirect addressing by using the representation for memory accesses in Problem
8.6
.
Chapter Notes
The classification of languages by the resources needed for their recognition is a very large
subject capable of topic-length study. The reader interested in going beyond the introduc-
tion given here is advised to consult one of the readily available references. The
Handbook of
Theoretical Computer Science
contains three survey articles on this subject by van Embde Boas
[
350
], Johnson [
151
], and Karp and Ramachandran [
161
]
Search WWH ::
Custom Search