Def: A ( nondet) off – line TM is a 6 – tuple M =(S, Σ ...



UNIT 2 Tractable and Intractable problems

Lemma Let f be a det N ( N. f(n) ≥ [pic] n . Let f1 : N ( N f1(n) ≤ f(n). for all but finitely many n . Then DTIME (f1) [pic] DTIME (f)

Proof Let L[pic] DTIME (f1) . By definition, ( a deterministic TM [pic] L = T(M) = T(M. f1). By hypothesis, there are only finitely many integers x [pic] f1(x) > f(x). Therefore there are only finitely many strings x [pic] x [pic] T(M1 f1) = T(M) but not in T(M1 f). Let M1 be a TM [pic] for each of these strings x in T(M1 f1 ) but not in T(M1 f ), the Turing Machine M1 accepts using its finite state control. M1 is constructed in such a way that , for any x [pic] T(M1 f1 ) but not in M1 f ) , M1 takes |x| steps to recognize the string x and accepts it. Therefore, M1 operates in such a way that

time M1 (x) = { timeM (x) if x [pic] T(M1 f)

= { |x| if x [pic] T(M1 f1 )

Since f(x) ≥ x it follows that time M1 (x) ≤ f( |x| ) for all x.

Hence L= T(M1) = T(M 1 , f) ( L [pic] DTIME (f) .

Eg. f 1 (x) = 3n + 5 f ( x) = 4n

f 1 (x) ≤ f (x) for all n ≥ 5

3n+ 5 ≤ 4n ( 4n – 3n > 5 ( x > 5

only for n = 0, 1, 2, 3, 4 that

f 1 (x) > f (x)

| |n = 0 |n = 1 |n = 2 |n = 3 |n = 4 |n = 5 |n = 6 |

|f 1 (n) |5 |8 |11 |14 |17 |20 |23 |

|f (n) |0 |4 |8 |12 |16 |20 |24 |

o M 1 accepts x in time f 1 but not in time f if | x | < 5.

o If M 1 accepts x in time f 1 but not in time f if | x | < 5 .

time M ( x ) = f ( | x | )

time M1 (x) = { f ( | x | ) if x [pic] T(M1 f)

= { | x | if x [pic] T(M1 f1 ) but x [pic] T(M1 f )

time M1 (x) ≤ f ( | x | ) since f ( n ) ≥ n [pic] n

Lemma 1.2 For any det. F : N ( N

DSPACE ( f (x ) ) = DSPACE (┌ f (n ) | 2 ┐) &

NSPACE ( f (x ) ) = NSPACE (┌ f (n ) | 2 ┐ )

Pf Let M = ( S, ∑ , [pic], δ , p0 , F ) be an off-line TM.

Let [pic] = { b1 , b2 , …. b k } . | [pic] | = k

Construct a new TM M 1 that uses k 2 worktape symbols : (b1 , b1 ) (b1 , b2 ) … , (b1 , b k ) … (b k , b1 ) .. (b k , b k ) . Using a symbol (b i , b j ) in one cell of its worktape M 1 will be able to represent 2 symbols b i & b j appearing in adjacent cells of the worktape of M.

M 1 will simulate M using one half of the worktape space. M 1 needs to keep track of which of the 2 symbols b i , b j M is currently scanning . It does this using state of the form ( p1 1) & ( p1 2) where p [pic] S .

M 1 = ( S 1 , ∑ , [pic]1 , δ 1 , Po1 , F1 ) where

S 1 = { ( p , 1 ) , ( p , 2 ) | p [pic] S }

┌1 = { (c , d) | c , d [pic] [pic] } U { B }

Po1 = { Po , 1}

F1 = { ( q, 1) (q , 2) | q [pic] F }

δ 1 is given below

( ( q,2) , X 1 , (c,d ) , P ) [pic] δ 1 ( (p, 1 ) , a , ( b ,d ) ) if

( q , X 1 , c, R ) [pic] δ (p, a , b)

( ( q, 1) , X1 , (c , d ) , P ) [pic] δ 1 ( (p, 1) , a , (b, d) ) if

(q , X1 , c, P ) [pic] δ( p, a, b)

( ( q, 2) , X1 , (c , d) , L ) [pic] δ 1 ( (p, 1) , a , (b, d) ) if

(q , X1 , c, L ) [pic] δ ( p, a, b)

( ( q, 1) , X1 , (b , d) , R ) [pic] δ 1 ( (p, 2) , a , (b, c) ) if

(q , X1 , d, R ) [pic] δ ( p, a, c)

( ( q, 2) , X1 , (b , d) , P ) [pic] δ 1 ( (p, 2) , a , (b, c) ) if

(q , X1 , d , P ) [pic] δ ( p, a, c)

( ( q, 1) , X1 , (b , d) , P ) [pic] δ 1 ( (p, 2) , a , (b, c) ) if

(q , X1 , d , L) [pic] δ ( p, a, c)

and for all state p [pic] S & symbols a [pic] ∑

( ( p, 1) , P , (B ,B) , P ) [pic] δ 1 ( (p, 1) , a ,B ) if

( ( p, 2) , P , (B ,B) , P ) [pic] δ 1 ( (p, 2) , a ,B )

Corollary For any det f: N ( N and any constant c ( 0 < c < 1 )

DSPACE (f (n)) = DSPACE ( c . f (n)) &

NSPACE (f (n)) = NSPACE ( c . f (n))

Pf For any const. c ( 0 < c < 1 ) ( k [pic] 1 / 2 k < c. Using previous lemma k times DSPACE (f (n)) ≤ DSPACE (┌ f (n ) | 2 k ┐) = DSPACE ( c.f(n)).

Examples of some computational problems

Clique of size and k problem

Input a finite undirected graph G = (V, E) & an integer k

Question Is there a set of k vertices or more { x, x2 , ... xk } in the G , for all i, j

1 ≤ i , j ≤ k { x i , x j } E ? ( In other words , is there a sub graph of G of size K or more which is a complete graph?

GAP

Input a finite directed graph G = (V, E) with a designated vertex s (the start node) and a set of designated vertices T (the set of goal node)

Question Is there a path from s to one of the vertices in T?

AGAP

Input a finite directed graph G = (V, E) and a labeling f: V {and, or}

Question Can a pebble be placed on a vertex with zero predecessors by placing the pebble game on G?

3-COLORABILITY

Input a finite undirected graph G = (V, E)

Question Is there a deterministic f: V {1, 2, 3} assigning the colors 1, 2 & 3 to the vertices of G [pic] {x, y} [pic] E f(x) [pic] f(y) ?

Pebble Problem

Input a finite directed graph G = {V, E} & k N

Question Can a pebble be placed on a vertex with zero predecessors Using at most k pebbles by playing the pebble game.

Clique (S) DSPACE ( log n)

Algorithm

i 1 ← 1

2 : i 2 ← i 1 +1

4 : i 4 ← i 2 +1

6 : i 6 ← i 3 +1

8 : i 8 ← i 4 +1

10: if : i 5 ≤ n then begin

if ( i1 , i 2 ) ( i1 , i 2 ) … ( i1 , i 5 )

( i1 , i 2 ) …………… ( i2 , i 5 )

( i3 , i 4 ) ( i3 , i 5 ) & ( i4 , i 5 ) [pic] E

then Answer “yes” the graph has a clique of size S.

Halt.

else

i 5 ← i 5 +1

Goto 10

End

else

i 4 ← i 4 +1

If i4 ≤ n then goto 8

If i3 ≤ n then goto 6

i 2 ← i 2 +1

if i 2 ≤ n then goto 4

i 1 ← i 1 +1

if i 1 ≤ n then goto 2

Answer no

Halt.

Construct a TM M which systematically has all possible sets of 5 vertices & check whether they form a clique.

For each set of 5 vertices M determines whether they is an edge between every pair of vertices in S. Each vertex is recorded on the worktape of TM M in binary notation. The representation of 5 vertices i1, i2, i3, i4, i5 : bin(i1 ) # bin(i2 ) # …. # bin(i5 ) # on the worktape . This requires 5.(log 2 n + 1)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download