Exercise Sheet 6: Diagonalisation - TU Dresden

2y ago
20 Views
2 Downloads
913.29 KB
16 Pages
Last View : 22d ago
Last Download : 2m ago
Upload by : Javier Atchley
Transcription

Exercise Sheet 6: DiagonalisationDavid CarralDecember 11, 2019

Exercise 1Find the fault in the following proof of P 6 NP.1. Suppose for a contradiction that P NP.2. By (1): since SAT NP, we have that SAT P.3. By (2): there is some k N with SAT DTime(nk ).4. Since SAT is NP-hard, we have that L p SAT for every language L NP.5. By (3) and (4): NP DTime(nk ).6. By (1) and (5): P DTime(nk ).7. By the Time Hierarchy Theorem, we have that DTime(nk ) DTime(nk 1 ).8. Conclusions (6) and (7) result in a contradiction. Hence, P 6 NP.Solution. In the previous argument, we cannot conclude (5) from (3) and (4).a. By the Time Hierarchy Theorem, there is some A DTime(nk 1 ) \ DTime(nk ).b. By (a): A P NP and hence, A p SAT.

Exercise 2Show the following.1. Time(2n ) Time(2n 1 )2. Time (2n ) Time (22n )3. NTime(n) PSpace

Exercise 2Solution 1. We show that Time(2n ) Time(2n 1 ).1. Since 2n O(2n 1 ), we have that L O(2n 1 ) for all L O(2n ).2. Since 2n 1 O(2n ), we have that L O(2n ) for all L O(2n 1 ).IIDefinition. g O(f ) iff there are some k, x0 0 with g (x) k · f (x) for all x x0 .2x 1 k · 2x for all x x0 with (e.g.) k 2 and x0 0.

Exercise 2Solution 2. We show that Time (2n ) Time (22n ).1. Time Hierarchy Theorem. If f , g : N N are such that f is time-constructibleand g · log g o(f ), then DTime (g ) DTime (f ).2. Definition. g o(f ) iff, for all ε 0, there is some x0 0 such thatg (x) ε · f (x) for all x x0 . Note that possibly ε 1.3. We have that 2n · log(2n ) o(22n ) since, for all ε 0, there is some x0 0 such2xxxthat 2x · x ε · 22x for all x x0 . Note that 22x·x x and ε·22x ε · 2 .4. By (1) and (3), DTime (2n ) DTime (22n ).

Exercise 2Solution 3. We show that NTime(n) PSpace.1. NTime(n) NSpace(n) because any TM that operates in time n on everycomputation branch can use at most n tape cells on every branch.2. By Savitch’s Theorem: NSpace(n) Space(n2 ).3. Space Hierarchy Theorem. If f , g : N N such that f is space-constructible andg o(f ), then DSpace(g ) DSpace(f ).4. By (3): Space(n2 ) Space(n3 ). Note that n2 o(n3 ).5. By (1), (2), (4), and Space(n3 ) PSpace: NTime(n) PSpace.

Exercise 3Show that there exists a function that is not time-constructible.Solution. The proof of the Gap Theorem explicitly constructs one.

Exercise 4Consider the function pad : Σ N Σ # defined as pad(s, ) s#j , wherej max(0, s ). In other words, pad(s, ) adds enough copies of a fresh symbol #to the end of s so that the length is at least .Examples.Ipad(01011, 8) 01011###Ipad(01011, 12) 01011#######Ipad(01011, 3) 01011For a language A Σ and a function f : N N, letpad(A, f ) { pad(s, f ( s )) s A }.

Exercise 4Let pad : Σ N Σ # be defined as pad(s, ) s#j , where j max(0, s ).For A Σ and f : N N, let pad(A, f ) { pad(s, f ( s )) s A }.Solution 1. We show that, if A DTime(n6 ), then pad(A, n2 ) DTime(n3 ).1. Let M be a DTM deciding A in O(n6 ) time.2. Let M0 be the TM that, on input w , performs the following computation:2.1 Reject if w is not of the form w s# with w s 2 .2.2 Simulate M on input s and return the result of the simulation.3. The check in (2.1) can be done in linear time using a 3-tape TM (discuss).Hence, it can be done in O(n2 ) with a single tape TM.4. Simulating M on s is O( s 6 ) O( w 3 ) O(n3 ).5. M0 runs in O(n3 ).6. M0 accepts s# iff s p s# and s A. That is, L(M0 ) pad(A, n2 ).Remarks:IThe choice of the particular numbers 2, 3, and 6 is arbitrary.IWe could make an analogous argument for space instead of time.IThe converse is also true.

Exercise 4Let pad : Σ N Σ # be defined as pad(s, ) s#j , where j max(0, s ).For A Σ and f : N N, let pad(A, f ) { pad(s, f ( s )) s A }.Solution 2. We show that if NExpTime 6 ExpTime, then P 6 NP.ddA DTime(2n ) pad(A, 2n ) P,dpad(A, 2n ) DTime(nk ) A ExpTimefor all k, d N. This also holds true for NTime instead of DTime.Then, assuming P NP, we can inferdA NExpTime A NTime(2n ) for some d Nd pad(A, 2n ) NP for some d Nd pad(A, 2n ) P for some d Nd pad(A, 2n ) DTime(nk ) for some d, k N A ExpTime

Exercise 4Let pad : Σ N Σ # be defined as pad(s, ) s#j , where j max(0, s ).For A Σ and f : N N, let pad(A, f ) { pad(s, f ( s )) s A }.Solution 3. We show that, for every A Σ and k N, A P iff pad(A, nk ) P.IA P implies pad(A, nk ) P.1. Let A Σ and k N.2. If A P, then A DTime(n ) for some N.3. pad(A, nk ) DTime(nd /ke ) P (analogous argument to the one from part 1).Ipad(A, nk ) P implies A P.1. If pad(A, nk ) P, then pad(A, nk ) DTime(n ) for some N.2. Therefore, A DTime(n ·k ) P.

Exercise 4Let pad : Σ N Σ # be defined as pad(s, ) s#j , where j max(0, s ).For A Σ and f : N N, let pad(A, f ) { pad(s, f ( s )) s A }.Solution 4. We show that P 6 DSpace(n).1. Assume P DSpace(n).2. By the space hierarchy theorem: There is some languageA DSpace(n2 ) \ DSpace(n).3. pad(A, n2 ) DSpace(n).4. pad(A, n2 ) P.5. A P.6. A DSpace(n).

Exercise 4Let pad : Σ N Σ # be defined as pad(s, ) s#j , where j max(0, s ).For A Σ and f : N N, let pad(A, f ) { pad(s, f ( s )) s A }.Solution 5. We show that NP 6 DSpace(n).1. We can make a similar argument to the one from (3) to show the following: forevery A Σ and k N, we have that A NP iff pad(A, nk ) NP.2. Then, make a similar argument to the one from (4) to show NP 6 DSpace(n).

Exercise 5You are given two oracles and one of them is the set TQBF, but you do not knowwhich one. Design a polynomial algorithm that decides TQBF using these oracles.IGiven a QBF formula φ y1 y2 . . . ym 1 ym .ψ(y1 , . . . , ym )IQuery φ with both oracles. Accept φ if both answer “true”, reject φ if bothanswer “false”, and otherwise play a game with two players: the -player, thatuses the accepting oracle, and the -player, that uses the rejecting oracle.IThe -player plays in turns i {1, 3, . . . , m 1} of the game. This player asks hisoracle both for b 0 and b 1 whether the formula yi yi 1 . . . Qm ym .ψ(x1 , . . . , xi 1 , b, yi 1 , . . . , ym ) is true or false. If both valuesare “false” then reject φ (the oracle is acting inconsistently). Otherwise, letxi b for a value b for which the answer was “true”.IThe -player plays in turns i {2, 4, . . . , m} of the game. This player asks hisoracle both for b 0 and b 1 whether the formula yi yi 1 . . . Qm ym .ψ(x1 , . . . , xi 1 , b, yi 1 , . . . , ym ) is true or false. If both valuesare “true” then accept φ (the oracle is acting inconsistently). Otherwise, letxi b for a value b for which the answer was “false”.IAccept φ iff ψ(x1 , . . . , xm ) evaluates to true (no need to use any oracles here!).

Exercise 4 Let pad: N ! # be de ned as pad(s;‘) s#j, where j max(0;‘j sj). For A and f : N !N, let pad(A;f) fpad(s;f(jsj)) js 2Ag. Solution 1. We show that, if A 2DTime(n6), then pad(A;n2) 2DTime(n3). 1.Let Mbe a DTM deciding A in O(n6) time. 2.Let M0be the TM that, on input w, performs the following computation: 2

Related Documents:

INDEX PRESENTATION 5 THE THUMB 7 MECHANICAL EXERCISES 8 SECTION 1 THUMB Exercise 1 12 Exercise 2 13 Exercise 3 - 4 14 Exercise 5 15 Estudio 1 16 SECTION 2 THUMB WITH JUMPS Exercise 6 17 Exercise 7 - 8 18 Exercise 9 19 Exercise 10 20 Exercise 11 - 12 21 Estudio 6 22 SECTION 3 GOLPE Exercise 13 23 Exercise 14 24 Exercise 15 25 Exercise 16 - 17 26 Exercise 18 27 .

Chapter 1 Exercise Solutions Exercise 1.1 Exercise 1.2 Exercise 1.3 Exercise 1.4 Exercise 1.5 Exercise 1.6 Exercise 1.7 Exercise 1.8 Exercise 1.9 Exercise 1.10 Exercise 1.11 Exercise 1.12 Fawwaz T. Ulaby and Umberto Ravaioli, Fundamentals of Applied Electromagnetics c 2019 Prentice Hall

Eigenvectors and diagonalisation Inner products and orthogonality Wrapping up Radboud University Nijmegen Last

Technical Report Number 806 Computer Laboratory UCAM-CL-TR-806 ISSN 1476-2986 On joint diagonalisation for dynamic network ana

Xu : A Diagonalisation Algorithm and Its Applications in Ambiguity Search 37 1 1 1 11 1 1 1 11 P E J P PA M A P P A M A P P P E J E J P T T T T T i.e., matrice

Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 2 Sheet 1 Sheet 3 Basic Information About Notes Lines and Spaces Trace Notes Stems Note Properties Writing Music Find the Way Home Crossword Puzzle Counting Notes Notes and Beats in 4/4 time Double Puzzle N

PLASKOLITE, INC. PRODUCTS: Acrylic Sheet Impact Modified Acrylic Sheet Copolyester Sheet Roll Stock Acrylic Sheet Colored Acrylic Sheet Patterned Sheet High Performance Coatings Thin & Thick Gauge Acrylic Sheet Frosted Acrylic Sheet Acrylic Sheet with Matte Finish Polystyrene Sheet Acrylic Mirror Sheet Acrylic

Abrasive water jet can do this with quality results but, generally is too expensive compared to plasma, laser or punching. 5. Cut Geometry Abrasive waterjet cuts have straight edges with a slight amount of taper. Kerf width is controlled by the orifice/nozzle combination. Cuts in thicker materials generally require larger combinations with more abrasive usage. The kerf width can be as small as .