Information Technology Reference
In-Depth Information
8.1
Introduction
The classification of problems requires a precise definition of those problems and the com-
putational models used. Problems are accurately classified only when we are sure that they
have been well defined and that the computational models against which they are classified are
representative of the computational environment in which these problems will be solved. This
requires the computational models to be general. On the other hand, to be useful, problem
classifications should not be overly dependent on the characteristics of the machine model used
for classification purposes. For example, because of the obviously inefficient use of memory on
the Turing machine, the set of problems that runs in time linear in the length of their input on
a random-access machine is likely to be different from the set that runs in linear time on the
Turing machine. On the other hand, the set of problems that run in polynomial time on both
machines is the same.
8.2 Languages and Problems
Before formally defining decision problems, a major topic of this chapter, we give two examples
of them,
SATISFIABILITY
and
UNSATISFIABILITY
. A set of clauses is
satisfiable
if values can
be assigned to Boolean variables in these clauses such that each clause has at least one literal
with value 1.
SATISFIABILITY
Instance:
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
.
Answer:
“Yes” if for some assignment of Boolean values to variables in
{
x
1
,
x
2
,
...
,
x
n
}
,at
least one literal in each clause has value 1.
The complement of the decision problem
SATISFIABILITY
,
UNSATISFIABILITY
,isdefined
below.
UNSATISFIABILITY
Instance:
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
.
Answer:
“Yes” if for all assignments of Boolean values to variables in
{
x
1
,
x
2
,
...
,
x
n
}
,all
literals in at least one clause have value 0.
The clauses
C
1
=(
{
x
1
,
x
2
,
x
3
}
{
x
1
,
x
2
}
{
x
2
,
x
3
}
)
ar
e satisfie
d
with
x
1
=
x
2
=
x
3
=
1,
,
,
whereas the clauses
C
2
=(
)
are not
satisfiable.
SATISFIABILITY
consists of collections of satisfiable clauses.
C
1
is in
SATISFIABIL
-
ITY
. The complement of
SATISFIABILITY
,
UNSATISFIABILITY
, consists of instances of clauses
not all of which can be satisfied.
C
2
is in
UNSATISFIABILITY
.
We now introduce terminology used to classify problems. This terminology and the asso-
ciated concepts are used throughout this chapter.
{
x
1
,
x
2
,
x
3
}
{
x
1
,
x
2
}
{
x
2
,
x
3
}
{
x
3
,
x
1
}
{
x
1
,
x
2
,
x
3
}
,
,
,
,
DEFINITION
8.2.1
Let
Σ
be an arbitrary finite alphabet. A
decision problem
P
is defined by a
set of
Σ
∗
of the problem and a condition
φ
P
:
I
instances
I
⊆
→B
that has value
1
on “Yes”
instances and
0
on “No” instances. Then
I
yes
=
{
w
∈
I
|
φ
P
(
w
)=
1
}
are the “Yes” instances.
The “No” instances are
I
no
=
I
−
I
yes
.
Search WWH ::
Custom Search