[PDF] Tutorial 10 Prove that the class P

View - Download Tutorial 10

Previous PDF

Next PDF

COMPUTABILITY ANDCOMPLEXITYTUTORIAL10Tutorial 10

Exercise 1 (compulsory)

Consider the following context-free grammarGin Chomsky normal form: S!AAj

A!BBjABja

B!BAjb

Following the algorithm in the proof of Theorem 7.16 (see also Lecture 10 and your notes) compute the entriestable(i;j)for all1ij4in order to show thatabba2L(G).

Solution:

l= 11234 1A 2B 3B

4Al= 21234

1AA 2BA 3BB 4A l= 31234

1AAS;A

2BAA;S

3BB

4Al= 41234

1AAS;AS;A

2BAA;S

3BB 4A Notice thatSappears in the entry(1;4), which implies thatabba2L(G).Exercise 2 (compulsory) Prove that the class P is closed under intersection, complement and concatenation.

Solution:

Intersection.LetL1;L22P. We want to show thatL1\L22P. BecauseL12P then there exists a TMM1with time complexityO(nk1)for some constantk1. BecauseL22P then there exists a TMM2with time complexityO(nk2)for some constantk2. We construct a deciderMwith polynomial time complexity decidingL1\L2:

M= "On inputx:

1.

Run M1on inputx

2.

If M1accepted, then runM2on inputx, else reject.

3.

If M2also accepted, then accept, else reject."

In the worst caseMwill run bothM1andM2, in which case it usesO(nk1) +O(nk2)steps. Let k= max(k1;k2). We then see thatMhas time complexityO(nk)and henceL(M) =L1\L22P. (Note that we omitted the details where a copy of the stringxfor the machineM2is stored while the machineM1is computing; this can be done e.g. on a second tape but we know that all deterministic variants of Turing machines are polynomial-time equivalent.) 1

COMPUTABILITY ANDCOMPLEXITYTUTORIAL10Complement.The same construction as for decidable languages (see e.g. slide 13 in Lecture 3). We

simply swap the accept and reject state. The running time of the modified machine does not change. Concatenation.We want to show that ifL1;L22P thenL1L22P. Assume so thatL12P and thatL22P. By definition, this means that there exist decidersM1andM2such thatM1is a decider forL1with time complexityO(nk1)andM2is a decider forL2with time complexityO(nk2)for some constantsk1andk2.

The concatenationL1L2is defined as

L

1L2=fx1x2jx12L1;x22L2g

The decider forL1L2must, given an inputx, try to find a partition ofxintox1x2such thatx12L1 andx22L2. Here is the decider: "On inputx=a1:::an 1.

F ori= 0tondo

i. Let x1=a1:::aiandx2=ai+1:::an. (By agreementa1:::a0=and a n+1:::an=). ii.

Run M1on the inputx1.

iii.

Run M2on the inputx2.

iv. If both M1andM2accepted, then accept2.If no choice of x1andx2led to acceptance, then reject" We must now show that the decider has polynomial time complexity. The main loop of the decider is traversed at most (n+1)-times. If we runM1on a substring ofx, this will take at mostO(nk1) steps. Similarly, runningM2on a substring ofxwill take at mostO(nk2)steps. Consequently, a single traversal of the loop body uses no more thanO(nk1) +O(nk2) =O(nk)steps, where k= max(k1;k2). The whole decider thus uses(n+ 1)O(nk) =O(nk+1)steps. HenceL(M) = L

1L22P.Exercise 3 (compulsory)

Prove the following theorem.

Theorem:Lett(n)nbe a function from natural numbers to positive reals. Then for every language L2NTIME(t(n))there is a constantcsuch thatL2TIME(2ct(n)).

Solution:

This is in fact a simple test on applying the definitions and Theorem 7.11 on page 260. Assume a languageL2NTIME(t(n))for some functiont(n)n. By definition of NTIME there is a nondeterministic single-tape TMMrunning in timeO(t(n))and decidingL. By Theorem 7.11 we know that forMwe can construct an equivalent TMM0such thatM0is a single-tape deterministic decider for Lrunning in time2O(t(n)). Because2O(t(n))meansO(2ct(n))for some constantc, we get (by definition) thatL2TIME(2ct(n))and we are done.Exercise 4 (compulsory) Every week someone manages to "prove" that P=NP or that P6=NP. Last week a very famous professor published the following proof that P6=NP:

Proof:Consider the following decider forHAMPATH:

2 COMPUTABILITY ANDCOMPLEXITYTUTORIAL10"On inputhG;s;ti: 1. Generate all possible permutations of nodes from G. 2. If one of these permuations (sequences of nodes )forms a Hamiltonian path, then accept . 3.

Otherwise reject ."

Because there aren!different permuations of nodes to examine, the algorithm clearly does not run in polynomial time. Therefore we have proved thatHAMPATHhas exponential time complexity and this meansHAMPATH62P. Because we know thatHAMPATH2NP, we conclude that P6=NP.

Describe the error in the above proof.

Solution:

It is true that the suggestedalgorithmforHAMPATHdoes not run in polynomial time, but from this fact we cannot conclude that thelanguageHAMPATHdoes not belong to the class P. There can still be other

(faster) algorithms forHAMPATHthat run in polynomial time; we simply did not exclude this possibility

by presenting one particular algorithm with an exponential running time. To conclude thatHAMPATH62

P we would have to shownoalgorithm forHAMPATHhas a polynomial time complexity.Exercise 5 (optional, but highly recommended)

Prove that the class P is closed under Kleene star. (Hint:use dynamic programming.)

Solution:

LetA2P. We want to show thatA2P. SinceA2P there exists a deterministic Turing machineMA with time complexityO(nk)for somek0. We now build, usingMA, a deterministic decider forAand show that its time complexity is bounded by a polynomial. The central observation in our construction is thatw2Aif and only if one of the following conditions is true w=", or w2A, or

9 u;v:w=uvandu2Aandv2A.

In the decider described below we letwi;jdenote the substring ofw=w1w2:::wnstarting withwi and ending withwj. The decider builds a table wheretable(i;j) =trueifwi;j2A. We do this by

considering all substrings ofwstarting with substrings of length1and ending with the substring of length

n. "On inputw=w1w2:::wn:

1. Ifw="then accept, else

2. For`:= 1ton

3. Fori:= 1ton(`1)

4.j:=i+`1

5. RunMAonwi;j

6. IfMAacceptswi;jthentable(i;j) :=true

7. Else

8. Fork:=itoj1

9. Iftable(i;k) =trueandtable(k+ 1;j) =true

10. thentable(i;j) :=true

11. Iftable(1;n) =truethen accept, else reject."

We now analyze the complexity of our decider. The algorithm uses three nested loops, each of which can be traversed at mostO(n)times. In the second loop we runMAon an input of length at mostn, so the total time is at mostO(n)O(n)(O(nk) +O(n)) =O(n2+(max(k;1)))steps, which is polynomial inn. 3quotesdbs_dbs17.pdfusesText_23

[PDF] p ? q is logically equivalent to

[PDF] p ? q ? p ? q

[PDF] p(anb) formule

[PDF] p (q p) is equivalent to

[PDF] p toluene diazonium chloride

[PDF] p value excel

[PDF] p.c. sharma machine design pdf

[PDF] p.o. box 188004 chattanooga

[PDF] p.o. box 5008 brentwood

[PDF] p100 mask

[PDF] p2p car sharing business model

[PDF] p65warnings

[PDF] p7 design and implement a security policy for an organisation

[PDF] p7zip command line

[PDF] pa 1040 form 2019 pdf