算法作业

NP章第三题

首先，可知STINGY SAT的解可以在多项式的时间内得出，因此属于NP，另外很容易得知SAT可以归为STINGY SAT问题，于是就可以得出STINGY SAT是NP完全问题。以上

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

推荐阅读更多精彩内容

  • 算法(12)- NP完全性
    P L是{0, 1}* 的子集, 如果对任意的输入串x, 算法都能在多项式时间内判定(decide)x是否属于L,...
    陈码工阅读 3,280评论 0赞 2
  • Shell 编程
    Kali-LinuxShell编程 【课程目的】 1.掌握shell的基本命令 2.掌握shell的基本概念和作用...
    FX喂你袋盐阅读 397评论 0赞 0
  • for循环里的setTimeout
    第一个： 第一个输出 的结果是4,4,4,4 第二个： 第二个输出 的结果是0，1，2，3 用的是闭包,也有人称为...
    小盼珂阅读 459评论 0赞 0