Show that if P = NP, a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. (See the note in Problem 7.38.)

Problem 7.38.

Show that if P = NP, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. Note: The algorithm you are asked to provide computes a function; but NP contains languages, not functions. The P = NP assumption implies that SAT is in P, so testing satisfiability is solvable in polynomial time. But the assumption doesn’t say how this test is done, and the testmay not reveal satisfying assignments. Youmust show that you can find them anyway. Hint: Use the satisfiability tester repeatedly to find the assignment bit-by-bit.