Information Technology Reference
In-Depth Information
SEQUENCING
problem. Then the following inequality holds:
⎛
⎞
r
⎝
⎠
≤
[
if
a
π
(
1
)
+
a
π
(
2
)
+
···
+
a
π
(
j
)
>d
,
then
a
π
(
j
)
else
0
]
k
j
=
1
Let
q
be the expression in parentheses in the above inequality. Then
q
=
a
π
(
l
+
1
)
+
a
π
(
l
+
2
)
+
···
+
a
π
(
n
)
,where
l
is the integer for which
p
=
a
π
(
1
)
+
a
π
(
2
)
+
···
+
a
π
(
l
)
≤
d
and
p
+
a
π
(
l
+
1
)
>d
.Bydefinition
p
+
q
=
i
a
i
. It follows that
q
≥
i
a
i
−
d
.Since
k
=
i
a
i
−
q
d
, we conclude that
p
=
d
or that the instance of
TASK SEQUENCING
corresponds to a “Yes” instance of
SUBSET SUM
. Similarly, consider a “Yes” instance of
SUBSET SUM
. It follows from the above argument that there is a permutation such that the
instance of
TASK SEQUENCING
is a “Yes” instance.
≤
The following
NP
-complete problem is closely related to the
P
-complete problem
LINEAR
INEQUALITIES
. The difference is that the vector
x
must be a 0-1 vector in the case of 0-1
INTEGER PROGRAMMING
,whereasin
LINEAR INEQUALITIES
it can be a vector of rationals.
Thus, changing merely the conditions on the vector
x
elevates the problem from
P
to
NP
and
makes it
NP
-complete.
0-1
INTEGER PROGRAMMING
Instance:
An
n
×
m
matrix
A
and a column
n
-vector
b
, both over the ring of integers for
integers
n
and
m
.
Answer:
“Yes” if there is a column
m
-vector
x
over the set
{
0, 1
}
such that
A
x
=
b
.
THEOREM
8.10.8
0-1
INTEGER PROGRAMMING
is
NP
-complete.
Proof
To s h ow t h a t 0 - 1
INTEGER PROGRAMMING
is in
NP
,wenotethata0-1vector
x
can be chosen nondeterministically in
n
steps, after which verification that it is a solution to
the problem can be done in
O
(
n
2
)
steps on a RAM and
O
(
n
4
)
steps on a DTM.
To s h ow t h a t 0 - 1
INTEGER PROGRAMMING
is
NP
-hardwegivealog-spacereduc-
ti
on of 3-
SAT
to i
t.
Given an instance of 3-
SAT
, namely, a set of literals
X
=(
x
1
,
x
1
,
x
2
,
x
2
,
...
,
x
n
,
x
n
)
and a sequence of clauses
C
=(
c
1
,
c
2
,
...
,
c
m
)
, where each clause
c
i
is a subset of
X
containing at most three literals, we construct an
m
×
p
matrix
A
=[
B
|
C
]
,
where
B
=[
b
i
,
j
]
for 1
pm
.We
also construct a column
p
-vector
d
as shown below, where
p
=(
m
+
1
)
n
.Theentriesof
B
and
C
are defined below.
b
i
,
j
=
1f
x
j
∈
≤
i
,
j
≤
n
and
C
=[
c
r
,
s
]
for 1
≤
r
≤
n
and 1
≤
s
≤
c
i
for 1
≤
j
≤
n
−
1f
x
j
∈
c
i
for 1
≤
j
≤
n
c
r
,
s
=
−
1f
(
r
−
1
)
n
+
1
≤
s
≤
rn
0 th rwe
Since no one clause contains both
x
j
and
x
j
, this definition of
a
i
,
j
is consistent.
We a l so l e t
d
i
,the
i
th component of
d
,satisfy
d
i
=
1
q
i
,where
q
i
is the number of
complemented variables in
c
i
.Thus,thematrix
A
has the form given below, where
B
is an
m
−
×
n
matrix and each row of
A
contains
n
instances of -1 outside of
B
in non-overlapping
Search WWH ::
Custom Search