a. Define what f(n) = O(g(n)) means. Define the complexity classes P and NP. [5 marks]...

  

Transcribed Image Text:

a. Define what f(n) = O(g(n)) means. Define the complexity classes P and NP. [5 marks] b. We proved in class that the problem CLIQUE is NP-complete by con- structing a polynomial reduction from 3SAT to CLIQUE. i Given an input formula = (PVQVR) A (PV-Q) A (-Q V R) construct a graph G that is the result of applying the reduction. [4 marks] ii In the reduction, what is the size k of the clique that G has if y is satisfiable? [2 marks] iii Does G indeed have a clique of size k (that you computed in the previous subquestion)? If yes, show it on the graph (list the nodes and edges) and explain how you can construct a satisfying assignment to from it. If G does not have a clique of size k, explain why does not have a satisfying assignment. [4 marks] a. Define what f(n) = O(g(n)) means. Define the complexity classes P and NP. [5 marks] b. We proved in class that the problem CLIQUE is NP-complete by con- structing a polynomial reduction from 3SAT to CLIQUE. i Given an input formula = (PVQVR) A (PV-Q) A (-Q V R) construct a graph G that is the result of applying the reduction. [4 marks] ii In the reduction, what is the size k of the clique that G has if y is satisfiable? [2 marks] iii Does G indeed have a clique of size k (that you computed in the previous subquestion)? If yes, show it on the graph (list the nodes and edges) and explain how you can construct a satisfying assignment to from it. If G does not have a clique of size k, explain why does not have a satisfying assignment. [4 marks]

Answer rating: 100% (QA)

a 1 fn Ogn This notation means that the ... View the full answer