Game Development Reference
In-Depth Information
q =
s |
q and s
q }
lower bound is q
{
s
s
. We view antichains
as a symbolic representation of
-downward-closed sets of cells. Given an
s
s }
antichain q
∈A
, let q
=
{
s
S
|∃
q : s
be the downward
closure of q , i.e., the set of cells that it represents.
Exercise 6.9
are indeed the operators of least upper
bound and greatest lower bound respectively. By establishing this, you have
shown that the set of antichains forms a complete lattice. What are the least
and greatest elements of this complete lattice ?
To define a controllable predecessor operator Cpre A over antichains, we
observe that for all q
Show that
and
A ,
s
q : post σ ( s )
s }
Cpre( q
)=
{
s
S
|∃
σ
Σ
·∀
o
∈O·∃
o
pre σ ( s
s
=
{
s
S
|∃
σ
Σ
·∀
o
∈O·∃
q : s
o )
}
pre σ ( s )=
| post σ (
where o = L
\
o and
{
L
{
}
)
s
}
. Hence, we define
Cpre A ( q )=
σ∈ Σ
pre σ ( s
o )
s ∈q
o∈O
and this operator computes a symbolic representation of the controllable
predecessors of the downward-closed set of cells symbolically represented
by q .
, we have Cpre A ( q )
Lemma 6.7
For all antichains q
∈A
= Cpre( q
) .
Exercise 6.10 Prove Lemma 6.7.
In the definition of Cpre A , the operations
pre, σ∈ Σ and s ∈q can be
computed in polynomial time, while o∈O can be computed in exponential
time by simple application of the definitions. Unfortunately, it turns out that
a polynomial-time algorithm is unlikely to exist for computing o∈O as the
NP-complete problem IndependentSet can be reduced to it.
Consider a graph G =( V,E ) where V is a set of vertices and E ⊆ V × V
is a set of edges. An independent set of G is a set W ⊆ V of vertices such
that for all ( v, v ) ∈ E , either v ∈ W or v ∈ W , i.e., there is no edge of
G connecting vertices of W . The IndependentSet problem asks, given a
graph G and size k , to decide if there exists an independent set of G of size
larger than k . This problem is known to be NP-complete. We show that
IndependentSet reduces to computing
.
E let q e = V
=( V,E ) be a graph, and for each e =( v, v )
Let
G
\
v } . The set q e
{
contains all sets of vertices that are independent
of the edge e . Therefore, the antichain q =
v
}
,V
\{
e∈E q e
contains the maximal