NP-complete

  • P是指多项式时间内解决的问题
  • NP是能在多项式时间验证答案正确与否的问题
  • P是否等于NP是在问，如果一个问题我们能够在多项式时间内验证其答案的正确性，那么我们能否在多项式时间内解决它？
  • 称问题L是NP-hard，如果任意一个NP问题都可以多项式规约到L。
  • 如果一个NP-hard的问题L本身是NP的，则称L是NP-complete

ref
zhihu:怎么理解P问题与NP问题

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。