Tutorial 13 PDF Prove that the class NP

CSE105 Homework 3

P is closed under complement. For any P-language L let M be the TM that decides it in polynomial time. We construct a TM M' that decides the complement of

Tutorial 10

Prove that the class P is closed under intersection complement and concatenation. Solution: • Intersection. Let L1

Exercise Sheet 9

Since P is closed under complement (Le)e is in P and we can conclude that L ∈ P. Exercise 9.2 (Reduction). Given an undirected graph G := 〈G

Counting classes: thresholds parity

and fewness”

Complexity classes defined by counting quantifiers

closed under complement. Symmetric difference. Let LI Lz be two sets in CK Three relativizations have been given

Limits of Computation: Homework 4 solutions

23 февр. 2001 г. If P=NP then since P is closed under complement

Theory of Computation

5 нояб. 2013 г. If P = NP then NP is also closed under complementation. In other words

CSE105 Homework 3

P is closed under complement. For any P-language L let M be the TM that decides it in polynomial time. We construct a TM M' that

Exercise Sheet 9

Exercise 9.1 (P). (a) Show that P is closed under union complement

Tutorial 10

Prove that the class P is closed under intersection complement and concatenation. Solution: • Intersection. Let L1

Homework 11 Solutions

(c) Show that P is closed under complementation. Answer: Suppose that language L1 ? P so there is a polynomial-time TM M1 that decides L1. A Turing machine M2

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

Counting classes: thresholds parity

and fewness”

Tutorial 13

Prove that the class NP is closed under union intersection

Advanced Complexity

4 oct. 2017 The converse problem is in NP and PSPACE is stable by complement ... only if M does not accept w (PSPACE is closed under complementation).

8.6 Complements of Complexity Classes

the regular languages are closed under complementation. However we ... In particular

COMPUTABILITY AND COMPLEXITY TUTORIAL - UMD

Prove that the class P is closed under intersection complement and concatenation Solution: Intersection Let L 1;L 2 2P We want to show that L 1 L 2 2P Because L 1 2P then there exists a TM M 1 with time complexity O(nk 1) for some constant k 1 Because L 2 2P then there exists a TM M 2 with time complexity O(nk 2) for some constant k 2

P NP and NP-Completeness - Princeton University

P vs NP Not much is known unfortunately Can think of NP as the ability to appreciate a solution P as the ability to produce one P NP Dont even know if NP closed under complement i e NP = co-NP? Does L NP imply ? NP?

CSE105 Homework 3

P is closed under complement For any P-language L let M be the TM that decides it in polynomial time We construct a TM M’ that decides the complement of L in polynomial time: M’= “On input : 1 Run M on w 2 If M accepts reject If it rejects accept ” M’ decides the complement of L Since M runs in polynomial time M’ also

P and NP Closure Properties 1 Closure Properties for P - UMD

Polynomials are closed under many oper-ations (e g addition multiplication) hence P is closed under many operations (e g concatention) Classes likeDT IM E(n)and evenDT IM E(O(n)) are thought to not be closed under concatenation and many other operations (We do not know ifthey are ) Theorem 2 LetL2P ThenL 2P Proof

Chapter 24 coNP Self-Reductions - University of Illinois

24 2 1 5 P is closed under complementation Proposition 24 2 3 Decision problem X is in P if and only if X is in P Proof: (A) If X is in P let A be a polynomial time algorithm for X (B) Construct polynomial time algorithm A? for X as follows: given input x A? runs A on x and if A accepts x A? rejects x and if A rejects x then A

Searches related to p is closed under complement filetype:pdf

of P from PSPACE for which polynomial-time reductions are appropriate We now consider po-tential separations of classes within P and from NP For these complexity classes the notion of polynomial-time mapping reductions is too coarse since it does not distinguish L from P We need a ?ner notion of reduction De?nition 1 1

Is NP closed under complement?

Also, if NP is not closed under complement, then P != NP. The converse of "If P=NP, then NP is closed under complement" would be "If NP is closed under complement, then P=NP". However, this is not known to be true: it is possible that NP is closed under complement but is still different from P. Thanks for the correction @DavidRicherby.

How to prove that class P is closed under intersection complement and concatenation?

Prove that the class P is closed under intersection, complement and concatenation. Solution: Intersection. Let L 1;L 22P. We want to show that L 1L 22P. Because L 12P then there exists a TM M 1with time complexity O(nk 1) for some constant k 1. Because L 22P then there exists a TM M 2with time complexity O(nk 2) for some constant k 2.

What is the complementary event of P?

Complementary event of P will be (1 - Probability of event occurred). Login Study Materials BYJU'S Answer NCERT Solutions NCERT Solutions For Class 12 NCERT Solutions For Class 12 Physics

How do you know if a class is closed under complement?

A class is said to be closed under complement if the complement of any problem in the class is still in the class. Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class.

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.

Sho wthat NOTAis NP-complete.

Solution:

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.

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

ONMLHIJKx+

ONMLHIJKGFED@ABCxONMLHIJKGFED@ABC

yONMLHIJK xQ yG

GGGGGGGGGGGGGGGGGGGGGGGGGGGGG

ONMLHIJKGFED@ABCy9

9999999

ONMLHIJKy

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

[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

[PDF] Tutorial 13 Prove that the class NP

Is NP closed under complement?

How to prove that class P is closed under intersection complement and concatenation?

What is the complementary event of P?

How do you know if a class is closed under complement?

COMPUTABILITY ANDCOMPLEXITYTUTORIAL13Tutorial 13

Exercise 1 (compulsory)

Solution:

1.Intersection:

M= "On inputw:

1. RunM1onw. IfM1rejected then reject.

2. Else runM2onw. IfM2rejected then reject.

3. Else accept."

2.Union:

M= "On inputw:

1. RunM1onw. IfM1accepted then accept.

2. Else runM2onw. IfM2accepted then accept.

3. Else reject."

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."

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."

VERTEX-COVERPA. The reduction is

Solution:

Express this problem as a language called NOTA.

Sho wthat NOTAis NP-complete.

Solution:

The language is:

Here is a polynomial-time NTM decidingNOTA:

Ev aluatewith this truth assignment.

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

Output h:i."

Consider the following formulain cnf.

2_x3_x

Solution:

The formula0is

2_z)^(z_x3_x

1_x4_x

Consider the following formulain 3-cnf.

Solution:

ONMLHIJKGFED@ABC

ONMLHIJKGFED@ABCyONMLHIJKy

ONMLHIJKGFED@ABC

ONMLHIJKx+

ONMLHIJKGFED@ABCxONMLHIJKGFED@ABC

GGGGGGGGGGGGGGGGGGGGGGGGGGGGG

ONMLHIJKGFED@ABCy9

9999999

ONMLHIJKy

9999999

ONMLHIJKGFED@ABCy9

9999999