A joke(continued) Why? no body in the company has taken C$4335 Explanation: Euler circuit problem can be easily solved in polynomial time Hamilton circuit problem is proved to be NP-hard So far, no body in the world can give a polynomial time algorithm for a np-hard problem Conjecture: there does not exist polynomial time algorithm for this problem 2021/26 CS4335 Design and Analysis of2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 19 A joke (continued): Why? no body in the company has taken CS4335. Explanation: Euler circuit problem can be easily solved in polynomial time. Hamilton circuit problem is proved to be NP-hard. So far, no body in the world can give a polynomial time algorithm for a NP-hard problem. Conjecture: there does not exist polynomial time algorithm for this problem