Information Technology Reference
In-Depth Information
that it doesn't and establish a contradiction. Since
G
doesn't have a three-coloring, there is
an edge
e
=(
v
,
w
)
such that
c
v
=
c
w
, which contradicts the assumption that
S
has an
exact cover. It follows that
G
has a three-coloring if and only if
S
has an exact cover.
SUBSET SUM
Instance:
Aset
Q
=
of positive integers and a positive integer
d
.
Answer:
“Yes” if there is a subset of
Q
that adds to
d
.
{
a
1
,
a
2
,
...
,
a
n
}
THEOREM
8.10.6
SUBSET SUM
is
NP
-complete.
Proof
SUBSET SUM
is in
NP
because a subset can be nondeterministically chosen in time
equal to
n
and an accepting choice verified in a polynomial number of steps by adding up
the chosen elements of the subset and comparing the result to
d
.
To s h ow t h a t
SUBSET SUM
is
NP
-hard, we give a log-space reduction of
EXACT COVER
to it. Given an instance of
EXACT COVER
, namely, a set
S
=
{
u
1
,
u
2
,
...
,
u
p
}
and a family
{
of subsets of
S
,weconstructtheinstanceof
SUBSET SUM
characterized
as follows. We let
β
=
n
+
1and
d
=
β
n−
1
+
β
n−
2
+
S
1
,
S
2
,
...
,
S
n
}
+
β
0
=(
β
n
···
−
1
)
/
(
β
−
1
)
.We
S
by the integer
β
i−
1
,1
represent the element
u
i
∈
n
, and represent the set
S
j
by
the integer
a
j
that is the sum of the integers associated with the elements contained in
S
j
.
For example, if
p
=
n
=
3,
S
1
=
≤
i
≤
{
u
1
,
u
3
}
,
S
2
=
{
u
1
,
u
2
}
,and
S
3
=
{
u
2
}
,werepresent
S
1
by
a
1
=
β
2
+
β
0
,
S
2
by
a
2
=
β
+
β
0
,and
S
3
by
a
3
=
β
.Since
S
1
and
S
3
forms an
exact cover of
S
,
a
1
+
a
3
=
β
2
+
β
+
1
=
d
.
Thus, given an instance of
EXACT COVER
, this polynomial-time transformation pro-
duces an instance of
SUBSET SUM
. We now show that the instance of the former is a “Yes”
instance if and only if the instance of the latter is a “Yes” instance. To see this, observe that
in adding the integers corresponding to the sets in an
EXACT COVER
in base
β
there is no
carry from one power of
β
to the next. Thus the coefficient of
β
k
is exactly the number
of times that
u
k
+
1
appears in each of the sets corresponding to a set of subsets of
S
.The
subsets form a “Yes” instance of
EXACT COVER
exactly when the corresponding integers
contain each power of
β
exactly once, that is, when the integers sum to
d
.
TASK SEQUENCING
Instance:
Positive integers
t
1
,
t
2
,
...
,
t
r
,whichare
execution times
,
d
1
,
d
2
,
...
,
d
r
,which
are
deadlines
,
p
1
,
p
2
,
...
,
p
r
,whichare
penalties
,andinteger
k
≥
1.
Answer:
“Yes” if there is a permutation
π
of
{
1, 2,
...
,
r
}
such that
⎛
⎞
r
⎝
⎠
≤
[
if
t
π
(
1
)
+
t
π
(
2
)
+
···
+
t
π
(
j
)
>d
π
(
j
)
then
p
π
(
j
)
else
0
]
k
j
=
1
THEOREM
8.10.7
TASK SEQUENCING
is
NP
-complete.
Proof
TASK SEQUENCING
is in
NP
because a permutation
π
for a “Yes” instance can be
verified as a satisfying permutation in polynomial time. We now give a log-space reduction
of
SUBSET SUM
to
TASK SEQUENCING
.
An instance of
SUBSET SUM
is a positive integer
d
and a set
Q
=
of
positive integers. A “Yes” instance is one such that a subset of
Q
adds to
d
.Wetranslate
an instance of
SUBSET SUM
to an instance of
TASK SEQUENCING
by setting
r
=
n
,
{
a
1
,
a
2
,
...
,
a
n
}
t
i
=
p
i
=
a
i
,
d
i
=
d
,and
k
=(
i
a
i
)
−
d
. Consider a “Yes” instance of this
TASK
Search WWH ::
Custom Search