1. Homepage
2. Homework
3. Theories of Computation: Summative Assignment 3: CLIQUE problem and polynomial bounds
This question has been solved

# Theories of Computation: Summative Assignment 3: CLIQUE problem and polynomial bounds

Theories of ComputationCLIQUE problemCLIQUE ReductionSAT

Theories of Computation: Summative Assignment 3 To be handed in on Canvas before Tuesday 25th April, 12pm An undirected graph G consists of vertices and edges, and its sizeis the number of vertices. For example, here are two undirected graphs of size 4: 0 1 2 3G1=0 1 2 3G2= We take the vertices to be numbered 0;1;:::;n1, wherenis the size of the graph. A clique in G is a set of vertices with any two distinct vertices appearing in the list are related by an edge. The CLIQUE problem consists in deciding whether a given undirected graph G contains a clique of a given size. For example,G1contains a clique of length 3 but G2does not. Apropositional formula 'is constructed from atoms and the connectives :,_and^. The sizej'jof a formula is the number of occurences of atoms in it. An assignment gives value True orFalse to each atom; it is satisfying for a formula 'if it makes the formula True . The S ATproblem consists in deciding whether a given formula 'has a satisfying assignment. The purpose of this exercise is to establish a polytime reduction from C LIQUE to S AT.

1. Let’s ﬁrst consider one instance: deciding whether G1above contains a clique of size 3. We’ll deﬁne a propo-
sitional formula '3
G1= 3
G1^ 3
G1that has a satisfying assignment if and only if G1has a clique of size 3. (It
does, but imagine that we do not yet know this.)
Such a clique, if it exists, can be listed in increasing order. For i<3andp< 4, the atomxi;pmeans thatpis the
ith element of the list. This forms our set At=fx0;0;:::;x 0;3;x1;0;:::;x 1;3;x2;0;:::;x 2;3gof propositional
atoms.
The ﬁrst part of the formula will be
3
G1= (x0;0_x0;1_x0;2_x0;3)^(x1;0_x1;1_x1;2_x1;3)^(x2;0_x2;1_x2;2_x2;3)^
((x0;0^x0;1)(x0;0^x0;2)(x0;0^x0;3)(x0;1^x0;2)(x0;1^x0;3)_(x0;2^x0;3))^
((x1;0^x1;1)(x1;0^x1;2)(x1;0^x1;3)(x1;1^x1;2)(x1;1^x1;3)_(x1;2^x1;3))^
((x2;0^x2;1)(x2;0^x2;2)(x2;0^x2;3)(x2;1^x2;2)(x2;1^x2;3)(x2;2^x2;3)) to express having a list of 3vertices ofG1. Write a formula 3 G1, shorter than 3 G1, to express that the list is in increasing order and represents a clique. Hint: First describe the relationship between the 0th and 1st element of the list. For example, for G2above, it would be (x0;0^x1;2)(x0;1^x1;2)_(x0;1^x1;3). There is no need to use negation in your formula. [3 marks] 1
2. Now let us extend this deﬁnition to 'k G= k G^ k Gfor an undirected graph Gof any sizenand anykn. Again, if a clique exists, it can be listed in increasing order. For i<k andp<n , the atomxi;pmeans thatpis theith element of the list. To begin, we write k G=^ i<k p<nxi;p! ^^ i<k: p<q<n(xi;p^xi;q)! to express having a list of kvertices ofG. Give a formula k Gto express that the list is in increasing order and represents a clique. The set of edges is writtenE, so(p;q)2Emeans that there is an edge from ptoq. [3 marks]
3. Show that the size of 'k Gis polynomially bounded by the size of G, that is, there exists a polynomial Psuch thatj'k GjP(n). Hint: You can ﬁnd polynomial bounds for j k Gjand forj k Gjindependently. This means that you can partially answer this question even if you could not answer the previous ones. [3 marks]
4. It follows that the time taken to construct 'k G fromGis polynomial in the size of G(since we can check in linear time whether (p;q)2E). Using what you know about the SAT problem, explain in a few lines what you could deduce about the C LIQUE problem if it were the case that P=NP. [3 marks]

## Get in Touch with Our Experts QQ WeChat Whatsapp
Theories of Computation代写,CLIQUE problem代写,CLIQUE Reduction代写,SAT代写,Theories of Computation代编,CLIQUE problem代编,CLIQUE Reduction代编,SAT代编,Theories of Computation代考,CLIQUE problem代考,CLIQUE Reduction代考,SAT代考,Theories of Computationhelp,CLIQUE problemhelp,CLIQUE Reductionhelp,SAThelp,Theories of Computation作业代写,CLIQUE problem作业代写,CLIQUE Reduction作业代写,SAT作业代写,Theories of Computation编程代写,CLIQUE problem编程代写,CLIQUE Reduction编程代写,SAT编程代写,Theories of Computationprogramming help,CLIQUE problemprogramming help,CLIQUE Reductionprogramming help,SATprogramming help,Theories of Computationassignment help,CLIQUE problemassignment help,CLIQUE Reductionassignment help,SATassignment help,Theories of Computationsolution,CLIQUE problemsolution,CLIQUE Reductionsolution,SATsolution,