知识卡片

普通读书笔记卡 · 3714.b.3

电路可满足性提供归约起点

理解等级:中级

证明新的NP完全问题通常需要一个已知的NP完全起点。

书中以电路可满足性为起点:给定AND、OR、NOT组合电路,问是否有布尔输入使输出为1。其NP完全性证明安排在本章后文。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      A first NP-complete problem Because the technique of reduction relies on having a problem already known to be NP-complete in order to prove a different problem NP-complete, there must be some “first” NP-complete problem. We’ll use the circuit-satisfiability problem, in which the input is a boolean combinational circuit composed of AND, OR, and NOT gates, and the question is whether there exists some set of boolean inputs to this circuit that causes its output to be 1. Section 34.3 will prove that this first problem is NP-complete. Chapter outline This chapter studies the aspects of NP-completeness that bear most directly on the analysis of algorithms. Section 34.1 formalizes the notion of

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[10000,15000))。 - 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与NP的未解关系写成已证明结论。 - 原始内容:A first NP-complete problem Because the technique of reduction relies on having a problem already known to be NP-complete in order to prove a different problem NP-complete, there must be some “first” NP-complete problem. We’ll use the circuit-satisfiability problem, in which the input is a boolean combinational circuit composed of AND, OR, and NOT gates, and the question is whether there exists some set of boolean inputs to this circuit that causes its output to be 1. Section 34.3 will prove that this first problem is NP-complete. Chapter outline This chapter studies the aspects of NP-completeness that bear most directly on the analysis of algorithms. Section 34.1 formalizes the notion of