Prove the following claim. If L1 E NP and L2 EP then LU L2 E NP....

Transcribed Image Text:

Prove the following claim. If L1 E NP and L2 EP then LU L2 E NP. First (i) formulate what you assume and what you want to construct, then (ii) write down the proof/construction and (iii) provide a complexity analysis of your construction so that you can argue that the union belongs to the class NP. Prove the following claim. If L1 E NP and L2 EP then LU L2 E NP. First (i) formulate what you assume and what you want to construct, then (ii) write down the proof/construction and (iii) provide a complexity analysis of your construction so that you can argue that the union belongs to the class NP.