3. a) With brief explanation, determine the complexity class of the following problems: i. Given a chessboard configuration, is A to B the next best move? ii. Given a graph, is there a negative cycle or not? iii. Given a program P, will it halt? iv. Given a set of clauses C, C, ..., Ck, each of length 3, over variables X = :{X1, X,..., n}, is there a satisfying assignment? b) Finding all pair shortest path in a graph - is in P and also in NP. Justify the statement.