Information Technology Reference
In-Depth Information
P
P
The
complement of a decision problem
, denoted
co
, is the decision problem in which
P
P
the “Yes” instances of
co
and vice versa.
The “Yes” instances of a decision problem are encoded as binary strings by an
encoding func-
tion
σ
:Σ
∗
→B
∗
that assigns to each
w
are the “No” instances of
∈B
∗
.
∈
I
astring
σ
(
w
)
With respect to
σ
,the
language
L
(
P
)
associated with a decision problem
P
is the set
L
(
P
)=
{
σ
(
w
)
|
w
∈
I
yes
}
.Withrespectto
σ
,thelanguage
L
(
co
P
)
associated with
co
P
is the
set
L
(
co
P
)=
{
σ
(
w
)
|
w
∈
I
no
}
.
The
complement of a language
L
, denoted
L
,is
B
∗
−
L
;thatis,
L
consists of the strings
that are not in
L
.
A decision problem can be generalized to a
problem
B
∗
→
P
characterized by a function
f
:
B
∗
described by a set of ordered pairs
(
x
,
f
(
x
))
,whereeachstring
x
∈B
∗
appearsonceasthe
B
∗
→B
left-hand side of a pair. Thus, a
language
is defined by problems
f
:
and consists of the
strings on which
f
has value
1
.
SATISFIABILITY
and all other decision problems in
NP
have succinct “certificates” for
“Yes” instances, that is, choices on a nondeterministic Turing machine that lead to acceptance
of a “Yes” instance in a number of steps that is a polynomial in the length of the instance. A
certificate for an instance of
SATISFIABILITY
consists of values for the variables of the instance
on which each clause has at least one literal with value 1. The verification of such a certificate
can be done on a Turing machine in a number of steps that is quadratic in the length of the
input. (See Problem
8.3
.)
Similarly,
UNSATISFIABILITY
and all other decision problems in
coNP
can be disqualified
quickly; that is, their “No” instances can be “disqualified” quickly by exhibiting certificates for
them (which are certificates for the “Yes” instance of the complementary decision problem).
For example, a disqualification for
UNSATISFIABILITY
is a satisfiable assignment for a “No”
instance, that is, a satisfiable set of clauses.
It is not known how to identify a certificate for a “Yes” instance of
SATISFIABILITY
or any
other
NP
-complete problem in time polynomial in length of the instance. If a “Yes” instance
has
n
variables, an exhaustive search of the 2
n
values for the
n
variables is about the best general
method known to find an answer.
8.2.1 Complements of Languages and Decision Problems
There are many ways to e
nc
ode problem instances. For example, for
SATISFIABILITY
we
might represent
x
i
as
i
and
x
i
as
i
and then use th
e
standard seven-bit ASCII encodings for
characters. Then we would translate the clause
∼
{
x
4
,
x
7
}
{
∼
}
and then represent it as
123 052 044 126 055 125, where each number is a decimal representing a binary 7-tuple and
4, comma, and
into
4,
7
are represented by 052, 044, and 126, respectively, for example.
All the instances
I
of decision problems
∼
considered in this chapter are characterized
by regular expressions. In addition, the encoding function of Definition
8.2.1
can be chosen
to map strings in
I
to binary strings
σ
(
I
)
describable by regular expressions. Thus, a finite-
state machine can be used to determine if a binary string is in
σ
(
I
)
or not. We assume that
membership of a string in
σ
(
I
)
can be dete
r
mined efficiently.
As suggested by Fig.
8.1
,thestringsin
L
(
P
P
)
, the complement of
L
(
P
)
, are either strings
)
or strin
gs
in
σ
(Σ
∗
−
I
)
. Since testing of membership in
σ
(Σ
∗
−
in
L
(
co
P
I
)
is easy, testing
for membership in
L
(
)
requires about the same space and time. For this reason,
we often equate the two when discussing the complements of languages.
P
)
and
L
(
co
P
Search WWH ::
Custom Search