原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
its output. You can see the value in having a polynomial-time algorithm for this problem.
Given a circuit C, you can determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if the circuit has k inputs, then you would have to check up to 2k possible assignments. When the size of C is polynomial in k, checking all possible assignments to the inputs takes Ω(2k) time, which is superpolynomial in the size of the circuit.10 In fact, as we have claimed, there is strong evidence that no polynomial-time algorithm exists that solves the circuit-satisfiability problem because circuit satisfiability is NP-complete. We break the proof of this fact into two parts, based on the two parts of the definition of NP-completeness. Lemma 34.5 The circuit-satisfiability problem belongs to the class NP. Proof We provide a two-input, polynomial-time
algorithm A that can verify CIRCUIT-SAT. One of the inputs to A is (a standard encoding o
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea