打开主菜单
描述P, NP, NP完全,以及NP困难之间关系的欧拉图

介绍NP困难之前要说到P问题和NP问题,P问题就是在多项式时间内可以被解决的问题,NP问题就是在多项式时间内可以被验证其正确性的问题。 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.