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