Information Technology Reference
In-Depth Information
1.2.1 The Class NP
∩
co
NP
ˇ
∗
\
The class coNP consists of languages
L
such that
L
is in NP.
Indeed, for any class of languages
C
we can define co
C
:
ↆ
ˇ
∗
|
ˇ
∗
\
co
C
={
L
L
∈
C
}
.
Remark 2.2
The
class coNP consists of all languages whose complem
ents a
re in NP.
For example SAT is in coNP and, by virtue of SAT being NP-complete, SAT is coNP-
complete under polynomial-time many-one reductions. The set TAUT consisting of
all propositional tautologies is also coNP-complete (exercise: verify this). Whether
NP equals coNP is a major open problem. We can view the NP versus coNP question
from the logical perspective of propositional proof systems. For any language
L
∈
NP, by definition for each
x
L
there is a polynomial-length proof of membership
that can be checked in polynomial time. This can be thought of as a “sound and
complete proof system” for
L
. Thus, the question whether NP
∈
coNP amounts to
asking if there is a proof system for propositional tautologies in which all tautologies
have polynomial length proofs. This leads to a study of propositional proof systems
of different strengths with the aim of proving lower bounds for proof lengths in the
proof systems. The article by Jacobo Torán in this volume presents aspects of this
fascinating topic with pointers to current research and open problems.
=
We will now discuss decision problems that are in NP
∩
coNP. For any
L
∈
NP
∩
coNP there are languages
A
and
B
in P and a polynomial
p
such that for each
∈
ˇ
∗
x
p
(
|
x
|
)
x
∈
L
ₔ∃
y
∈
ˇ
x
,
y
∈
A
p
(
|
x
|
)
ₔ∀
z
∈
ˇ
x
,
y
∈
B
These are the so-called well-characterized problems. They are well characterized
in the sense that membership of
x
in
L
can be characterized using an existentially
quantified predicate, and can also be characterized using a universally quantified
predicate. It is a remarkable phenomenon in complexity theory that the discovery of
such characterization often precedes (even anticipates) the discovery of a polynomial-
time algorithm for the problem. We discuss a few well-known examples.
The language PM
has a polynomial-time
algorithm as shown in the already mentioned famous paper of Edmonds [
Edm65
].
However, in the 1940s Tutte, in his well-known theorem stated below, had anticipated
this by “well-characterizing” the PM problem.
={
G
|
G
has a perfect matching
}
Theorem 2.3
(Tutte's 1-factor theorem) [
Tut47
]
An undirected graph G has a per-
fect matching if and only if for every subset S of the vertex set the number of odd-size
components in the graph G
\
S is bounded by
|
S
|
.
