原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
cuit can cause the output of the circuit to be 1. The circuit is therefore unsatisfiable.
Boolean combinational circuits contain no cycles. In other words, for a given combinational circuit, imagine a directed graph G = (V, E) with one vertex for each combinational element and with k directed edges for each wire whose fan-out is k, where the graph contains a directed edge (u, v) if a wire connects the output of element u to an input of element v. Then G must be acyclic. A truth assignment for a boolean combinational circuit is a set of
boolean input values. We say that a 1-output boolean combinational circuit is satisfiable
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea