sec exercises use reduction to prove that multiplying two upper triangular matrices is just as expensive (asymptoticallyas multiplying two arbitrary matrices (aexplain why computing the factorial of by multiplying all values from to together is an exponential time algorithm (bexplain why computing an approximation to the factorial of by making use of stirling' formula (see section is polynomial time algorithm consider this algorithm for solving the -clique problem firstgenerate all subsets of the vertices containing exactly vertices there are (nk such subsets altogether thencheck whether any subgraphs induced by these subsets is complete if this algorithm ran in polynomial timewhat would be its significancewhy is this not polynomial-time algorithm for the kclique problem write the sat expression obtained from the reduction of sat to sat described in section for the expression ( ( ( ( ( (bis this expression satisfiable draw the graph obtained by the reduction of sat to the -clique problem given in section for the expression ( ( ( ( cis this expression satisfiable hamiltonian cycle in graph is cycle that visits every vertex in the graph exactly once before returning to the start vertex the problem hamiltonian cycle asks whether graph does in fact contain hamiltonian cycle assuming that hamiltonian cycle is -completeprove that the decision-problem form of traveling salesman is -complete use the assumption that vertex cover is -complete to prove that kclique is also -complete by finding polynomial time reduction from vertex cover to -clique we define the problem independent set as follows