) State the input and output conditions of a decision problem version of Shortest Path. 2. (4 points) State the input and output conditions of a decision problem version of Travelling Salesperson. 3. (4 points) Alice recalls that Dijkstra’s algorithm solves the shortest path problem. She thinks this is sufficient to show Shortest Paths is in the complexity class P. Help Alice by showing that Shortest Paths can be solved, with help from Dijkstra’s algorithm, in polynomial time and thus that it is in P. 4. (4 points) Bob heard that the travelling salesperson problem is well known to be difficult. He suspects that it is not in the class P. However, he thinks it might be in the class NP. State a verification procedure for the travelling salesperson problem. 5. (4 points) Prove your verification procedure is correct and runs in polynomial time