登入選單

返回Google圖書搜尋

An Introduction to Circuit Complexity and a Guide to Håstad's Proof

Allan Heydon

出版	School of Computer Science, Carnegie Mellon University, 1990
URL	http://books.google.com.hk/books?id=Yi15PgAACAAJ&hl=&source=gbs_api

註釋

Abstract: "This report provides a complete exposition of the main proof in Johan Håstad's thesis [Hås87]. The result gives a lower bound on the size of certain Boolean circuits computing the PARITY function, and it implies that [formula]. Every effort has been made to make the proof understandable for someone with no background in the area of theoretical circuit complexity. To that end, the report begins by introducing the basic definitions and classes of the field. The proof is then motivated by a section explaining why circuits are of interest to theoretical computer scientists. Before stating and proving Håstad's result, some preliminary concepts are presented.