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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- what is a business line of credit
- what is a money line bet
- how tall is 1 6 m in feet
- what is a tuple in python
- what is a line chart
- tm 9 1005 319 10 operator s manual
- what is a manual line break
- is a picc line tunneled
- is a 6 6 a1c good
- is a 6 1 a1c bad
- what is a line of credit
- veggietales where s god when i m s scared