Information Technology Reference
In-Depth Information
Similarly, Farkas' lemma [
Sch98
, Sect. 7.3] stated below “well-characterizes”
linear programming which was shown to be in polynomial time many decades later
by Kachiyan [
Sch98
, Chap. 13].
Theorem 2.4
(Farkas' Lemma)
The system of linear inequalities Ax
≤
b has a
solution if and only if for all y
T
0
if y
T
A
0
then y
T
b
≥
=
≥
0
.
Exercise
Use the characterizations in Theorems 2.3 and 2.4 to show that the perfect
matching problem and feasibility of linear inequalities problem are in NP
∩
coNP.
Exercise
Show that NP
=
coNP if and only if some problem in NP
∩
coNP is
NP-complete.
The above discussion might lead one to believe that perhaps NP
∩
coNP equals P.
However, there are problems inNP
coNP that have defied all attempted polynomial-
time solutions. The decision version of the Integer factoring problem is a noteworthy
example. Each positive integer
n
can be uniquely factorized as
n
∩
p
e
1
p
e
2
,...,
p
e
k
=
where
p
1
<
p
2
<
···
<
p
k
are distinct primes. Let
enc
(
n
)
denote an encoding in
binary of this factorization. Consider the language
the
i
th
bit of
enc
FACT
={
n
,
i
,
b
|
(
n
)
is
b
}
.
Exercise
∩
1. Assuming primality testing is in P show that FACT is in NP
coNP.
2. Show that the integer factoring problem can be solved in polynomial time with
calls to a decision procedure for FACT.
1.3 The Berman-Hartmanis Conjecture
p
m
on NP languages that raises
some fundamental questions about the structure of NP languages.
Polynomial-time reductions define a natural order
≤
p
m
onNP languages is a binary relation that is reflexive
and transitive but not symmetric.
Exercise
Show that the order
≤
p
m
we define the equivalence relation
In order to obtain a partial order from
≤
p
m
B
if and only if
A
p
m
B
and
B
p
m
A
.
A
≡
≤
≤
Exercise
m
is an equivalence relation on NP.
1. Show that
≡
2. For
A
∈
NP let
[
A
]
denote the equivalence class containing
A
for the equivalence
m
. Show that
m
, suitably defined on the equivalences classes
relation
≡
≤
[
A
]
for
A
∈
NP, yields a partial order.
