Information Technology Reference
In-Depth Information
8.12 Show that the complexity class
P
is contained in the intersection of
NP
and
coNP
.
8.13 Demonstrate that
coNP
⊆
PSPACE
.
8.14 Prove that if a
coNP
-complete problem is in
NP
,then
NP
=
coNP
.
REDUCTIONS
P
1
and
P
2
are decision problems, a
Tu r i n g r e d u c t i o n
from
P
1
to
P
2
is any OTM
8.15 If
P
1
given an oracle for
P
2
. Show that the reductions of Section
2.4
are
that solves
Turing reductions.
8.16 Prove that the reduction given in Section
10.9.1
of a pebble game to a branching com-
putation is a Turing reduction. (See Problem
8.15
.)
8.17 Show that if a problem
P
1
can be Turing-reduced to problem
P
2
by a polynomial-time
P
1
is also in
P
.
Hint:
Since each invocation of the oracle can be done deterministically in polynomial
time in the length of the string written on the oracle tape, show that it can be done in
time polynomial in the length of the input to the OTM.
8.18 a) Show that every fixed power of an integer written as a binary
k
-tuple can be com-
puted by a DTM in space
O
(
k
)
.
b) Show that every fixed polynomial in an integer written as a binary
k
-tuple can be
computed by a DTM in space
O
(
k
)
.
Hint:
Show that carry-save addition can be used to multiply two
k
-bit integers with
work space
O
(
k
)
.
P
2
is in
P
,then
OTM and
HARD AND COMPLETE PROBLEMS
8.19 The class of polynomial-time Turing reductions are Turing reductions in which the
OTM runs in time polynomial in the length of its input. Show that the class of Turing
reductions is transitive.
P
-COMPLETE PROBLEMS
8.20 Show that numbers can be assigned to gates in an instance of
MONOTONE CIRCUIT
VALUE
that corresponds to an instance of
CIRCUIT VALUE
in Theorem
8.9.1
so that
the reduction from it to
MONOTONE CIRCUIT VALUE
can be done in logarithmic
space.
8.21 Prove that
LINEAR PROGRAMMING
described below is
P
-complete.
LINEAR PROGRAMMING
Instance:
Integer-valued
m
n
matrix
A
and column
m
-vectors
b
and
c
.
Answer:
“Yes” if there is a rational column
n
-vector
x
>
0suchthat
A
x
<
b
and
x
maximizes
c
T
x
.
×
NP
-COMPLETE PROBLEMS
8.22 A
Horn clause
has at most one
positive literal
(an instance of
x
i
). Every other literal
in a Horn clause is a
negative literal
(an instance of
x
i
).
HORN SATISFIABILITY
is an
Search WWH ::
Custom Search