作者sa074463 (垒包)
看板Grad-ProbAsk
标题[理工] [algo]-97清大
时间Mon Mar 1 15:27:26 2010
Read the following sentences and answer the questions.
NOTE that explanation is necessary
(a) It takes exponential number of steps to slove any NP-complete problem
in worst case
(b) The time complexity of any algorithm that solves a problem is an upper
bound on the time complexity of this problem
请问一下这两小题答案是什麽呢?
(a)是 polynomial number?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.62.73.138
1F:推 soldier723:指数吧 03/01 17:06
2F:推 FRAXIS:(a)只有在P!=NP的情况下才有可能成立 03/01 17:27
3F:→ FRAXIS:(b)是对的 因为可以知道只要花多少时间就可以解决这问题 03/01 17:28
4F:→ sa074463:恩谢谢你 03/01 23:09