NP困难：修订间差异

删除的内容添加的内容

行内

2023年3月27日 (一) 08:19的最新版本

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.

@@ 第1行： / 第1行： @@
 {{Expand|time=2013-03-12T12:00:33+00:00 }}
+{{NoteTA
-{{Unreferenced|time=2013-03-12T12:00:33+00:00 }}
+|G1 = IT
+}}
+{{distinguish|text=[[心灵哲学]]上的'''[[困难问题]]'''}}
+[[File:P np np-complete np-hard.svg|thumb|300px|描述[[P (复杂度)|P]], [[NP (复杂度)|NP]], [[NP完全]]，以及[[NP困难]]之间关系的[[欧拉图]]]]
+'''NP困难'''（'''NP-hardness''', non-deterministic polynomial-time hardness）问题是[[计算复杂性理论]]中最重要的[[复杂性类]]之一。如果所有[[NP (複雜度)|NP]]问题都可以[[多项式时间归约]]到某个问题，则称该问题为NP困难。
+因为NP困难问题未必可以在[[多项式时间]]内验证一个解的正确性（即不一定是NP问题），因此即使[[NP完全]]问题有多项式时间的解（[[P/NP问题#P=NP|P=NP]]），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。
-[[File:P np np-complete np-hard.svg|thumb|300px|描述[[P问题|P]], [[NP问题|NP]], [[NP完全]]，以及[[NP难]]之间关系的[[欧拉图]]]]
-'''NP困难'''（'''NP-hard''',non-deterministic polynomial-time hard）问题是[[计算复杂性理论]]中最重要的复杂性类之一。某个问题被称作NP困难，当所有[[NP]]问题可以在[[多项式时间图灵归约]]到这个问题。
+==参见==
-因为NP困难问题未必可以在多项式的时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间内的解（若[[P/NP问题#P.3DNP|P=NP]]），NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。
+* [[NP (複雜度)]]
+* [[NP完全]]
+* [[P/NP问题]]
+* [[歸約]]
+==參考文獻==
+{{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  |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.
+*Singh A, Krause A, Guestrin C, et al. Efficient informative sensing using multiple robots[J]. Journal of Artificial Intelligence Research, 2009, 34: 707-755.
+{{refend}}
 {{复杂度类}}
 [[Category:複雜度類]]
+[[Category:数学术语]]
-[[he:NP (מחלקת סיבוכיות)#NP-קושי ובעיות NP-שלמות]]