6.4 Nondeterministic Turing Machines 313
0
* 2. (a)0( ) CL2 = (21cx2c l l *cx&2cy 1 Xl,.. .,xm,y E {U,b}‘,(3il,.. .,ik) [l < -
il < l ** < ik < - m, xilxiz. b l xii, = y]}.A regular expression r is called a starless regzslar expression if it
does not contain the symbol * (the Kleene star). Show that the
problem of determining whether two starless regular expressions ~1
and ~2 are not equivalent (i.e., whether L(q) # L(Q)) is in NP.
Show that the problem of determining whether two regular expres-
sions are not equivalent is in NSPA CE( n).
An extended regulczr expression is a regular expression that can use
an additional intersection operation (denoted by 0). Show that the
problem of determining whether two extended regular expressions
are not equivalent is in Uc>0 NSPA CE (2”“).* 3. In the proof of Theorem 6.27, the predicate reach(al, CQ, ai) was solved
by a deterministic recursive algorithm. Convert it to an equivalent non-
recursive algorithm that uses space 0( (~(n))~).- Show that the complexity class NP is closed under union, intersection,
concatenation and Kleene closure. - Show that, for any real numbers T > - 1 and 0 < 6 < 1,
NSPACE(n’) s NSPACE(nr+E).* 6. (a) Show that Lemma 6.31 still holds if we replace the conditions
s2(n) > n and f(n) > n by s2(n) 2 logn and log(f(n)) =
O(s&z~). [Hint: Note that NTM A& can simulate A42 on input
Y- x$f(lXl)-lXl without writing down the string y on the second
tape. Instead, it may simply write down, in the second tape, the
position k of the input tape head of A& and use k to determine
what input symbol A4$s tape head is scanning.]
(b) Show that, f or any real numbers T > 0 and 0 < 6 < 1,NSPACE(n’) s NSPACE(n’+‘).- Show that iftl(n), tz(n), and f(n) are fully time-constructible functions
with tz(n) > n and f(n) > n, then NTIME(tl(n)) E NTIME(tz(n))
implies NTf?ME(tl(f(n))) c NTIME(t#(n))). - (a) Show that EXP # NP.
(b) Show that EXP # Uc>0 DTIME(2nC). - Show that if P = NP, then
u DTIME(2”=) = u NTIME(2nc).
c>o 00