chap limits to computation independent set inputa graph and an integer outputyes if there is subset of the vertices in of size or greater such that no edge connects any two vertices in sand no otherwise assuming that -clique is -completeprove that independent set is -complete define the problem partition as followspartition inputa collection of integers outputyes if the collection can be split into two such that the sum of the integers in each partition sums to the same amount no otherwise (aassuming that partition is -completeprove that the decision form of bin packing is -complete (bassuming that partition is -completeprove that knapsack is -complete imagine that you have problem that you know is -complete for this problem you have two algorithms to solve it for each algorithmsome problem instances of run in polynomial time and others run in exponential time (there are lots of heuristic-based algorithms for real -complete problems with this behavioryou can' tell beforehand for any given problem instance whether it will run in polynomial or exponential time on either algorithm howeveryou do know that for every problem instanceat least one of the two algorithms will solve it in polynomial time (awhat should you do(bwhat is the running time of your solution(cwhat does it say about the question of if the conditions described in this problem existed here is another version of the knapsack problemwhich we will call exact knapsack given set of items each with given integer sizeand knapsack of size integer kis there subset of the items which fits exactly within the knapsackassuming that exact knapsack is -completeuse reduction argument to prove that knapsack is -complete