← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.780Z

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 of) a boolean combinational circuit C. The other input is a certificate corresponding to an assignment of a boolean value to each of the wires in C. (See Exercise 34.3-4 for a smaller certificate.) The algorithm A works as follows. For each logic gate in the circuit, it checks that the value provided by the certificate on the output wire is correctly computed as a function of the values on the input wires. Then, if the output of the entire circuit is 1, algorithm A outputs 1, since the values assigned to the inputs of C provide a satisfying assignment. Otherwise, A outputs 0. Whenever a satisfiable circuit C is input to algorithm A, there exists a

certificate whose length is polynomial in the size of C and that causes A to output a 1.

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea