You are the interviewee during a job interview. The interviewer says, "I’ve a dynamic programming algorithm for the Subset-Sum p
roblem and its complexity is a polynomial of n and k", where n = |S| for an instance (S, k) of the SubsetSum problem. If you believe he found a polynomial time solution for a NP-complete problem, you should congratulate him for his success. If you don’t believe such an algorithm can exist, please point this out politely. If you think you can also create such an algorithm, please say so to the interviewer and do so here with the detailed time complexity analysis. What would be your response (you have to choose one of the three above with rationality)?