Bissoy.com
Doctors Medicines MCQs Q&A

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)? Correct Answer <img alt="F1 Raju Madhu 07.07.20 D9" src="//storage.googleapis.com/tb-img/production/20/07/F1_Raju_Madhu_07.07.20_D9.PNG" style="width: 216px; height: 100px;">

Clique is in NPC.

By definition of NPC, all NP problems can be reduced to Clique in polynomial time.

So, if clique can be solved in polynomial time, any NP problem can also be solved in polynomial time making P=NP and hence P=NP=NPC. 

Related Questions

The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
Horizontal clique, vertical clique and random clique are the examples of
The following Venn diagram gives data regarding the survey of a group of people in the state of Florida. The 'Circle' represents Asian; the 'Triangle' represents Scientists, the 'Rectangle' represents 'Professors' and the 'Quadrilateral' represents 'Africans. The numbers given in the diagram represents the number of that particular category. Based on the given diagram how many Asians are scientists as well as Professors?  
The following Venn diagram gives data regarding the survey of a group of people in state of Florida. The ‘Circle’ represents Asians; the ‘Triangle’ represents Scientists, the ‘Rectangle’ represents ‘Professors’ and the ‘Quadrilateral’ represents ‘Africans. The numbers given in the diagram represents number of persons of that particular category. Based on the given diagram how many Asians are scientists as well as Professors ?
A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i] = g (a[i] ) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below. Process X: private i; for (i=0; i
The given Venn diagram represents results of a class students: The triangle represents students who scored 85% and above in Maths, the circle represents students who scored 85% and above in English, the rectangle represents students who scored 85% and above in Science, and the square represents students who scored 85% and above in Social Science. The numbers given in the diagram represent the number of students in that particular category. How many students scored 85% and above in all the subjects?
In the Venn diagram given below, the circle represents ‘North Indian’, the triangle represents ‘Pianists’, the rectangle represents ‘Males’ and the square represents ‘Engineers’. The numbers given in the diagram represents number of persons of that particular category. Who among the following is a female- North Indian- Engineer?
In the given Venn diagram, the 'Triangle' represents 'females', 'Circle' represents 'graduates'; the 'Rectangle' represents 'Employed' and the 'Square' represents 'Youth(under 30 years)'. The numbers given in the diagram represents number of persons of that particular category. How many female graduates who are under 30 years are employed?
In the given Venn diagram, the square represents girls, the circle represents singers, the pentagon represents south Indians, and the rectangle represents graduates. The numbers given in the diagram represents the member of persons of that particular category. How many South Indian girls are singers but are not graduates ?
In the given Venn diagram, the ‘rectangle’ represents ‘ladies of a club’, the ‘triangle’ represents ‘like to dance’, the ‘circle’ represents ‘like to sing’ and the ‘pentagon’ represents ‘like to mimic’. The numbers given in the diagram represents the number of persons in that particular category. How many ladies of the club NEITHER like to dance NOR like to mimic?