Problem 1. Show that, if L;, Ly and Lg are 3 languages over © = {0,1} such that L; 2 clausesC1, ...,Ck and n variables x1, . . ., Zn, is there an assignment of the variables such that exactly k — 1...

PROBLEMS
Problem1
Show that if L1, L2, L3 are 3 languages over {0, 1} such that L1 <= L2 <= L3 then L1 <= L3.
If L1, L2, L3 are three languages with different grammar and rules, and it is given that the first language L1 <= second language L2.
Then by the normal rules of Grammar it is clear that L1 will also comes under L3.
i.e. if L1 <= L2
L2 <= L3
Then, L1 <= L3 will always be true.
Problem2
a) Can a Bipartite Graph with 8 vertices be Hamiltonian?
Ans: We know that a graph is Hamiltonian if it contains a Hamiltonian Cycle i.e., cycle containing all vertices of graph. So, A bipartite Graph with 8 (even) vertices can be Hamiltonian as there will be four-four vertices in both parts of the graph.
Consider X = {x1, x2, x3, … , xn}
     Y = {y1, y2, y3, … , yn}
Then, the Hamiltonian cycle can be formed in the graph as:
C = {x1, y1, x2, y2, x3, y3, … , xn, yn, x1}
Means a cycle can be formed that will cover all the vertices. Hence, A 8 vertices Bipartite Graph can be Hamiltonian.
b) Can a Bipartite Graph with 11 vertices be Hamiltonian?
Ans: No, A simple explanation of this is that a Bipartite Graph with odd number of vertices cannot have Hamiltonian cycle as every cycle in Bipartite Graph contains an even number of vertices & edges.
Problem3
a) Prove that APPROX-SAT is in NP.
To prove that APPROVE-SAT is NP then we have to first understand the problem. And the problem requires us to find if there is an group of variables such that k-1...