Database Reference
In-Depth Information
Clearly, finding a solution is at least as hard as deciding if it exists. The following theo-
rem implies that an algorithm for solution building with exponential combined complexity
is unlikely to exist. We show that the problem is N EXPTIME -complete, even for a simple
class of mapping. Just like NP-completeness implies an exponential-time algorithm (mod-
ulo some unresolved problems in complexity theory), N EXPTIME -complete is a strong
indication that doubly-exponential time is required.
Theorem 12.28
S OL E XISTENCE is N EXPTIME -complete.
The
problem
remains
N EXPTIME -hard for mappings from SM nr (
, ) .
Proof To get the upper bound proceed just like in the proof of Theorem 12.25 , only
instead of examining every possible kind K , choose it nondeterministically, together with a
witnessing run. Then, for each dependency
st and tuples a , b such
π ( x , z ) in
( x , y )
→∃
π
z
Σ
( a , b ), we need to check if there exists T
π ( a , z ).By
Lemma 12.29 below, this can be done nondeterministically in polynomial time.
L ( K ) such that T |
that T
|
=
π
=
Lemma 12.29
Fo r a n
A
-kind K, a pattern
π
, and a tuple a, satisfiability of
π
( a ) in a
tree agreeing with K can be witnessed by an object polynomial in the size of
π
, the height
and branching of K, and the size of
A
.
Proof We need to check if the ports of K canbefilledinsuchawaythat
( a ) is satisfied
in the resulting tree. The contexts/forests needed might be large, but just like in the proof
of Theorem 11.7 all we need is a support for the homomorphism from
π
( a ) to the tree. It is
easy to see that the total size of the support in the substituted parts can be bounded polyno-
mially. In particular, the number of ports involved in the realization of
π
( a ) is polynomial,
and for the remaining ones the support is empty. A homomorphism from
π
( a ) into K ex-
tended with the support can also be stored in polynomial memory. Verifying the witness
can be done in P TIME .
π
To get the lower bound we give a reduction from the following N EXPTIME -complete
problem: given a nondeterministic Turing machine M and n
, does M accept the empty
word in at most 2 n steps? The idea of the reduction is to encode the run of the machine in
the target tree. The run will be encoded as a sequence of 2 n configurations of length 2 n .
The machine M is stored in the source tree, except the (specially preprocessed) transition
relation, which is encoded in the target tree. The source tree is also used to address the
configurations and their cells.
We give a reduction of this problem to SM nr (
N
, , =).Removing= from the source side
is an instructive exercise (see Exercise 16.3 ).
Let M have the tape alphabet A with the blank symbol
A and the states q 0 , q 1 ,..., q f .
W.l.o.g. we assume that q f is the only final accepting state. The extended transition re-
lation of M , denoted
ˆ
, describes possible transitions in a window of three consecu-
tive tape cells. Formally,
δ
ˆ
A ) 6 ,where A is the set of decorated
δ
(
{
q 0 , q 1 ,..., q f ,
⊥}×
s , s , s s
tape symbols ,definedas A =
means “the head is else-
where”, marks the beginning of the tape, marks the end of the tape (at position 2 n ),
{
A
}
. The symbol
Search WWH ::




Custom Search