試題詳解

複選題
(57) Continuing the previous question, which of the following is wrong?
(A) Problem II can be solved with the Floyd-Warshall algorithm.
(B) An algorithm for Problem III can be used to find the longest path of a graph.
(C) If there is an algorithm that can find the longest path in a graph in polynomial time, then Problem III can be solved in polynomial time.
(D) Problem III can be reduced to Problem II by making each weight negative and thus can be solved with the Bellman-Ford algorithm.
(E) If Problem IIlI can be solved in polynomial time, then P=NP.