[PDF] [PDF] Tutorial 13

[PDF] Exercise Sheet 9

Exercise 9 1 (P) (a) Show that P is closed under union, complement, and concatenation (b) The complexity class coP contains all languages L whose 

[PDF] Notes on P Closed under Stuff - UMD CS

Prove that the class P is closed under intersection, complement and concatenation Solution: • Intersection Let L1,L2 ∈ P We want to show that L1 ∩ L2 ∈ P

[PDF] P and NP - UiO

P is closed under union, intersection, complement, and concatenation Additionally, polynomials are closed under addition and multiplication Closure under 

[PDF] Homework 11 Solutions

only if there exist positive constants c and n0 such that n2 ≤ cn log2 n for all n ≥ n0, which holds if (b) Show that P is closed under concatenation Answer: 

[PDF] Homework 02 - Undergraduate Complexity Theory

(a) (1 point ) Prove that the complexity class P is closed under complement (That is, show that if L ∈ P then Lc ∈ P, where Lc 

[PDF] Tutorial 13

Prove that the class NP is closed under union, intersection, concatenation and Kleene star Is the class NP closed also under complement? Solution:

[PDF] Chapter 2 : Time complexity - CSE IIT Kgp

(a) Demonstrate that the class P is closed under union, intersection, complement, concatenation and Kleene star (b) Prove that the class NP is closed under 

[PDF] Comp487/587 - Exercise 1

Problem 2: Closure of P Part 1: Prove that P is closed under union, intersection, and concatenation That is, if L1,L2 ∈ P, prove that each of the following are 

[PDF] CSE 6321 - Solutions to Problem Set 3

This means that P is closed under complement Based on the previous proof, we also have ¯L ∈ NP According to the definition of coNP, L ∈ coNP Thus,

[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

COMPUTABILITY ANDCOMPLEXITYTUTORIAL13Tutorial 13

Exercise 1 (compulsory)

Prove that the class NP is closed under union, intersection, concatenation and Kleene star. Is the class NP

closed also under complement?

Solution:

It is an open problem whether NP is closed under complement or not. The proofs for the remaining four

language operations can go as follows. Assume thatL1;L22NP. This means that there are nondetermin- istic decidersM1andM2such thatM1decidesL1in nondeterministic timeO(nk)andM2decidersL2in nondeterministic timeO(n`). We want to show that 1. there is a nondeterministic poly-time decider Msuch thatL(M) =L1\L2, and 2. there is a nondeterministic poly-time decider Msuch thatL(M) =L1[L2, and 3. there is a nondeterministic poly-time decider Msuch thatL(M) =L1L2, and 4. there is a nondeterministic poly-time decider Msuch thatL(M) =L1. Now we provide the four machinesMfor the different operations. The constructions are the standard

ones, the additional part is the complexity analysis of the running time. Note that we can use the power of

nondeterministic choices to make the constructions very simple.

1.Intersection:

M= "On inputw:

1. RunM1onw. IfM1rejected then reject.

2. Else runM2onw. IfM2rejected then reject.

3. Else accept."

Clearly, the longest branch in any computation tree on inputwof lengthnisO(nmaxfk;`g). SoMis a poly-time nondeterministic decider forL1\L2.

2.Union:

M= "On inputw:

1. RunM1onw. IfM1accepted then accept.

2. Else runM2onw. IfM2accepted then accept.

3. Else reject."

Clearly, the longest branch in any computation tree on inputwof lengthnisO(nmaxfk;`g). SoMis a poly-time nondeterministic decider forL1[L2. Note that in our case, we do not have the runM1 andM2in parallel, as it was necessary e.g. in the proof that recognizable languages are closed under union. Another possible construction would be to nondeterministically choose eitherM1orM2and simulate only the selected machine.

3.Concatenation:

M= "On inputw:

1. Nondeterministically splitwintow1,w2such thatw=w1w2.

2. RunM1onw1. IfM1rejected then reject.

3. Else runM2onw2. IfM2rejected then reject.

4. Else accept."

Clearly, the longest branch in any computation tree on inputwof lengthnis stillO(nmaxfk;`g) because step 1. takes onlyO(n)steps on e.g. a two tape TM. SoMis a poly-time nondeterministic decider forL1L2. 1 COMPUTABILITY ANDCOMPLEXITYTUTORIAL134.Kleene star:

M= "On inputw:

1. Ifw=then accept.2. Nondeterministically select a numbermsuch that1m jwj.

3. Nondeterministically splitwintompieces such thatw=w1w2:::wm.

4. For alli,1im: runM1onwi. IfM1rejected then reject.

5. Else (M1accepted allwi,1im), accept."

Observe that steps 1. and 2. take timeO(n), because the size of the numbermis bounded byn (the length of the input). Step 3. is also doable in polynomial time (e.g. by nondeterministically insertingmseparation symbols#into the input stringw). In step 4. the for loop is run at mostn times and every run takes at mostO(nk). So the total running time isO(nk+1). This means thatM is a poly-time nondeterministic decider forL1.Exercise 2 (compulsory) Consider the languageA=fanbnjn0g, which is a language in P. We will now try to show that

VERTEX-COVERPA. The reduction is

f(hG;ki) =aabbifGhas a vertex cover of sizek aabotherwise SinceVERTEX-COVERis NP-complete,VERTEX-COVERPAandA2P, we get that P=NP. Explain carefully what is the flaw is in this "proof".

Solution:

The problem with this "proof" is that the reduction is not known to be computable in polynomial time. For

this to be the case, we would have to prove that it is polynomial-time decidable ifGhas a vertex cover of

sizek. This is an open problem but many scientists think that it is indeed not the case (no such poly-time

algorithm exists), though there is no proof of this statement.Exercise 3 (compulsory) A Boolean formulais atautologyif every truth assignment will causeto evaluate to true. Consider the problem "Given a formula, is it the case thatisnota tautology?" 1.

Express this problem as a language called NOTA.

2.

Sho wthat NOTAis NP-complete.

Solution:

1.

The language is:

NOTA=fhi jis a Boolean formula which is not a tautologyg 2.

First note that a formula is not tautology e xactlywhen some truth assi gnmentcauses it to e valuateto

false. We now show thatNOTA2NP and thatSATPNOTA.

Here is a polynomial-time NTM decidingNOTA:

"On inputhi: 2 COMPUTABILITY ANDCOMPLEXITYTUTORIAL131.Guess a truth assignment. 2.

Ev aluatewith this truth assignment.

3.

If evaluates to false, then accept, else reject."

Letn=jj. This means thathas at mostndistinct variables; guessing truth values thus requires at mostO(n)steps. Evaluatingcan be done by scanning repeatedlyfrom left to right. This, too, requires only polynomially many steps. Consequently, the whole decider runs in nondeterministic polynomial time. We show thatSATPNOTAby giving the following reduction: "On inputhi: 1.

Output h:i."

Clearly, this reduction is computable in polynomial time andis not a tautology if and only if :is satisfiable.Exercise 4 (compulsory)

Consider the following formulain cnf.

(x1_x

2_x3_x

4)^(x 1_x4) Using the reduction described in the proof ofCNF-SATP3SATconstruct a formula0in 3-cnf such that is satisfiable if and only if0is satisfiable.

Solution:

The formula0is

(x1_x

2_z)^(z_x3_x

4)^(x

1_x4_x

1) wherezis a new (fresh) variable.Exercise 5 (compulsory)

Consider the following formulain 3-cnf.

(x_x_y)^(x_y_y)^(x_y_y) Using the reduction described in the proof of3SATPVERTEX-COVERconstruct an undirected graph Gand a numberksuch thatGhask-vertex cover if and only ifis satisfiable. List at least onek-vertex cover of the graph and find a corresponding satisfying truth assignment of the formula.

Solution:

Letkbe twice the number of clauses plus the number of variables, sok= 8in our case. The graphG 3 COMPUTABILITY ANDCOMPLEXITYTUTORIAL13looks as follows:

ONMLHIJKGFED@ABC

xONMLHIJKx

ONMLHIJKGFED@ABCyONMLHIJKy

ONMLHIJKGFED@ABC

x

ONMLHIJKx+

ONMLHIJKGFED@ABCxONMLHIJKGFED@ABC

yONMLHIJK xQ yG

GGGGGGGGGGGGGGGGGGGGGGGGGGGGG

ONMLHIJKGFED@ABCy9

9999999

ONMLHIJKy

9

9999999

ONMLHIJKGFED@ABCy9

9999999

The nodes marked by the double circle form an 8-vertex cover (note that there are more 8-vertex covers).

The corresponding satisfying assignment isx7!1,y7!1.Exercise 6 (optional) Consider the languageSUBSET-SUM. In its variant discussed in the book, we are given a multisetSof

numbers (that means that some of the numbers inScan repeat several times) and we try to select some of

the numbers fromSthat add up to a given numbert. We know that this problem is NP-complete. Show that a slight variant ofSUBSET-SUMwhereSis given as a set of numbers (which means that numbers cannot repeat) is also NP-complete. 4quotesdbs_dbs21.pdfusesText_27