| 单词 | np-complete |
| 释义 | > as lemmasNP-complete NP-complete adj. designating a member of a class of complex and intractable NP problems which can be converted into any other problem of the same class, such that if an algorithm for its solution in polynomial time existed, it would be possible to solve all NP problems in polynomial time; (of a problem) both NP and NP-hard. ΚΠ 1974 Proc. 6th Ann. ACM Symp. on Theory Computing 47/1 It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. 1998 Theoret. Computer Sci. 198 221 Contrary to..expectations, reachability turns out to be NP-complete. The NP-hardness proof is a straightforward reduction from the satisfiability problem for boolean formulas in conjunctive normal form. < as lemmas |
| 随便看 |
英语词典包含1132095条英英释义在线翻译词条，基本涵盖了全部常用单词的英英翻译及用法，是英语学习的有利工具。