a.Prove that the VC and the VCO are computationally equivalent b.Prove thatthe CLIQUE and the CLIQUEO are computationally equivalen

By assuming For each variable in C that satisfies The following
F = (CX1 ∨ CX2 ∨ CX4) ∧ (CX3 ∨ CX4) ∧ (CX2 ∨ CX3) ∧ and so on

Then for each node it will be

(CX1 = 0, CX2 = 0, CX4 = 0) (CX3 = 0, CX4 = 0) (CX2 = 0, CX3 = 0) . . .
(CX1 = 0, CX2 = 1, CX4 = 0) (CX3 = 0, CX4 = 1) (CX2 = 0, CX3 = 1)
(CX1 = 0, CX2 = 1, CX4 = 1) (CX3 = 1, CX4 = 1) (CX2 = 1, CX3 = 0)
(CX1 = 1, CX2 = 0, CX4 = 0)
(CX1 = 1, CX2 = 0, CX4 = 1)
(CX1 = 1, CX2 = 1, CX4 = 0)
(CX1 = 1, CX2 = 1, CX4 = 1)



We then place a position between 2 nodes if the partial assignments square measure
consistent. Notice that the utmost doable circle size is m as a result of there are not any
edges between any 2 nodes that correspond to an equivalent clause c. If the SAT satisfies
the assignment ,hence actually there's associate m-clique (just decide satisfies the
assignments then it will consist m nodes according...