NP困难：修订间差异
删除的内容 添加的内容
Charlesorium（留言 | 贡献） 无编辑摘要 |
小 使用HotCat已添加Category:数学术语 |
||
| （未显示4个用户的4个中间版本） | |||
| 第3行： | 第3行： | ||
|G1 = IT |
|G1 = IT |
||
}} |
}} |
||
{{distinguish|text=[[心灵哲学]]上的'''[[困难问题]]''}} |
{{distinguish|text=[[心灵哲学]]上的'''[[困难问题]]'''}} |
||
[[File:P np np-complete np-hard.svg|thumb|300px|描述[[P (复杂度)|P]], [[NP (复杂度)|NP]], [[NP完全]]，以及[[NP困难]]之间关系的[[欧拉图]]]] |
[[File:P np np-complete np-hard.svg|thumb|300px|描述[[P (复杂度)|P]], [[NP (复杂度)|NP]], [[NP完全]]，以及[[NP困难]]之间关系的[[欧拉图]]]] |
||
介绍'''NP困难'''之前要说到P问题和NP问题，'''P问题'''就是在多项式时间内可以被解决的问题，'''NP问题'''就是在多项式时间内可以被验证其正确性的问题。 |
|||
'''NP困难'''（'''NP-hardness''', non-deterministic polynomial-time hardness）问题是[[计算复杂性理论]]中最重要的[[复杂性类]]之一。如果所有[[NP (複雜度)|NP]]问题都可以[[多项式时间归约]]到某个问题，则称该问题为NP困难。 |
'''NP困难'''（'''NP-hardness''', non-deterministic polynomial-time hardness）问题是[[计算复杂性理论]]中最重要的[[复杂性类]]之一。如果所有[[NP (複雜度)|NP]]问题都可以[[多项式时间归约]]到某个问题，则称该问题为NP困难。 |
||
| 第18行： | 第17行： | ||
==參考文獻== |
==參考文獻== |
||
{{refbegin}} |
{{refbegin}} |
||
*{{cite book|author1 = Michael R. Garey |author2= David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} |
*{{cite book|author1 = Michael R. Garey |author2= David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness |url = https://archive.org/details/computersintract0000gare | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} |
||
*Hollinger G, Singh S. Multi-robot coordination with periodic connectivity[C]//Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010: 4457-4462. |
*Hollinger G, Singh S. Multi-robot coordination with periodic connectivity[C]//Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010: 4457-4462. |
||
*Singh A, Krause A, Guestrin C, et al. Efficient informative sensing using multiple robots[J]. Journal of Artificial Intelligence Research, 2009, 34: 707-755. |
*Singh A, Krause A, Guestrin C, et al. Efficient informative sensing using multiple robots[J]. Journal of Artificial Intelligence Research, 2009, 34: 707-755. |
||
| 第26行： | 第25行： | ||
[[Category:複雜度類]] |
[[Category:複雜度類]] |
||
[[Category:数学术语]] |
|||
2023年3月27日 (一) 08:19的最新版本
 | 此條目需要擴充。 (2013年3月12日) |
NP困难（NP-hardness, non-deterministic polynomial-time hardness）问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。
因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。
参见
[编辑]參考文獻
[编辑]- Michael R. Garey; David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979. ISBN 0-7167-1045-5.
- Hollinger G, Singh S. Multi-robot coordination with periodic connectivity[C]//Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010: 4457-4462.
- Singh A, Krause A, Guestrin C, et al. Efficient informative sensing using multiple robots[J]. Journal of Artificial Intelligence Research, 2009, 34: 707-755.
