Boolean functions and computation models
著者
書誌事項
Boolean functions and computation models
(Texts in theoretical computer science, An EATCS series)
Springer, c2010
大学図書館所蔵 件 / 全3件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references and index.
内容説明・目次
内容説明
The two internationally renowned authors elucidate the structure of "fast" parallel computation. Its complexity is emphasised through a variety of techniques ranging from finite combinatorics, probability theory and finite group theory to finite model theory and proof theory. Non-uniform computation models are studied in the form of Boolean circuits; uniform ones in a variety of forms. Steps in the investigation of non-deterministic polynomial time are surveyed as is the complexity of various proof systems. Providing a survey of research in the field, the book will benefit advanced undergraduates and graduate students as well as researchers.
目次
1. Boolean Functions and Circuits.- 2. Circuit Lower Bounds.- 3. Circuit Upper Bounds.- 4. Randomness and Satisfiability.- 5. Propositional Proof Systems.- 6. Machine Models and Function Algebras.- 7. Higher Types.- References.
「Nielsen BookData」 より