Evasiveness of graph properties and topological fixed-point theorems
著者
書誌事項
Evasiveness of graph properties and topological fixed-point theorems
（Foundations and trends in theoretical computer science, 7:4）
now, c2013
- : pbk
大学図書館所蔵 件 / 全1件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references (p. 79-81)
内容説明・目次
内容説明
Evasiveness of Graph Properties and Topological Fixed-Point Theorems addresses a fascinating topic that lies at the interface between mathematics and theoretical computer science. There have been several interesting research papers that use topological methods to prove lower bounds on the complexity of graph properties.
The goal of this text is to offer an integrated version of the underlying proofs in this body of research. While there are a number of very good expositions available on topological methods in decision-tree complexity, they all refer to other sources for the proofs of some topological results. This work is the first that provides a completely self-contained account. It begins by laying out the important foundational material and builds up to the more complex results at a steady pace. The capstone results, which consist of three lower bounds on the complexity of graph properties, appear in the final part of the text. The reader is not assumed to have any prior background in algebraic topology as all constructions from that subject are developed from scratch. The only prerequisite is a high level of comfort with discrete mathematics and linear algebra.
目次
Preface 1: Introduction 2: Basic Concepts 3: Chain Complexes 4: Fixed-point theorems 5: The decision-tree complexity of graph properties. A. Appendix. Acknowledgements. References.
「Nielsen BookData」 より