相关图书推荐
同类热销商品
您的浏览历史
通信复杂性与并行计算.（影印版）
|
|
促销活动
|
点击看大图基本信息
- 作者： Juraj Hromkovic
- 出版社：世界图书出版公司
- ISBN：7506247364
- 上架时间：2005-2-21
- 出版日期：2000 年6月
- 开本：32开
- 页码：336
- 版次：1-1
- 所属分类：
通信 >
通信技术理论与基础
内容简介回到顶部↑
The communication complexity of two-party protocols is an only 15 years old complexity measure, but it is already considered to be one of the fundamen- tal complexity measures of recent complexity theory. Similarly to Kolmogorov complexity in the theory of sequential computations, communication complex- ity is used as a method for the study of the complexity of concrete computing problems in parallel information processing. Especially, it is applied to prove lower bounds that say what computer resources (time, hardware, memory size) are necessary to compute the given task. Besides the estimation of the compu- tational difficulty of computing problems the proved lower bounds are useful for proving the optimality of algorithms that are already designed. In some cases the knowledge about the communication complexity of a given problem may be even helpful in searching for efficient algorithms to this problem.
The study of communication complexity becomes a well-defined indepen- dent area of complexity theory. In addition to a strong relation to several funda- mental complexity measures (and so to several fundamental problems of com- plexity theory) communication complexity has contributed to the study and to the understanding of the nature of determinism, nondeterminism, and random- ness in algorithmics. There already exists a non-trivial mathematical machinery to handle the communication complexity of concrete computing problems, which gives a hope that the approach based on communication complexity will be in- strumental in the study of several central open problems of recent complexity theory.
The study of communication complexity becomes a well-defined indepen- dent area of complexity theory. In addition to a strong relation to several funda- mental complexity measures (and so to several fundamental problems of com- plexity theory) communication complexity has contributed to the study and to the understanding of the nature of determinism, nondeterminism, and random- ness in algorithmics. There already exists a non-trivial mathematical machinery to handle the communication complexity of concrete computing problems, which gives a hope that the approach based on communication complexity will be in- strumental in the study of several central open problems of recent complexity theory.
目录回到顶部↑
1 Introduction
1.1 Motivation and Aims
1.2 Concept and Organization
1.3 How to Read the Book
2 Communication Protocol Models
2.1 Basic Notions
2.1.1 Introduction
2.1.2 Alphabets, Words, and Languages
2.1.3 Boolean Functions and Boolean Matrices
2.1.4 Representation of Computing Problems
2.1.5 Exercises
2.2 Communication Complexity According to a Fixed Partition
2.2.1 Definitions
2.2.2 Methods for Proving Lower Bounds
2.2.3 Theoretical Properties of Communication Complexity According to a Fixed Partition
2.2.4 Exercises
2.2.5 Research Problems
2.3 Communication Complexity
2.3.1 Introduction
2.3.2 Definitions
1.1 Motivation and Aims
1.2 Concept and Organization
1.3 How to Read the Book
2 Communication Protocol Models
2.1 Basic Notions
2.1.1 Introduction
2.1.2 Alphabets, Words, and Languages
2.1.3 Boolean Functions and Boolean Matrices
2.1.4 Representation of Computing Problems
2.1.5 Exercises
2.2 Communication Complexity According to a Fixed Partition
2.2.1 Definitions
2.2.2 Methods for Proving Lower Bounds
2.2.3 Theoretical Properties of Communication Complexity According to a Fixed Partition
2.2.4 Exercises
2.2.5 Research Problems
2.3 Communication Complexity
2.3.1 Introduction
2.3.2 Definitions
前言回到顶部↑
The communication complexity of two-party protocols is an only 15 years old complexity measure, but it is already considered to be one of the fundamen- tal complexity measures of recent complexity theory. Similarly to Kolmogorov complexity in the theory of sequential computations, communication complex- ity is used as a method for the study of the complexity of concrete computing problems in parallel information processing. Especially, it is applied to prove lower bounds that say what computer resources (time, hardware, memory size) are necessary to compute the given task. Besides the estimation of the compu- tational difficulty of computing problems the proved lower bounds are useful for proving the optimality of algorithms that are already designed. In some cases the knowledge about the communication complexity of a given problem may be even helpful in searching for efficient algorithms to this problem.
The study of communication complexity becomes a well-defined indepen- dent area of complexity theory. In addition to a strong relation to several funda- mental complexity measures (and so to several fundamental problems of com- plexity theory) communication complexity has contributed to the study and to the understanding of the nature of determinism, nondeterminism, and random- ness in algorithmics. There already exists a non-trivial mathematical machinery to handle the communication complexity of concrete computing problems, which gives a hope that the approach based on communication complexity will be in- strumental in the study of several central open problems of recent complexity theory.
This book presents the basic concepts in the study of communication com-plexity and in its application in proving lower bounds on distinct fundamental complexity measures. In the applications we focus on the complexity measures of realistic, parallel computing models like combinational (Boolean) circuits, VLSI circuits and interconnection networks. The book is written at a level ac- cessible to advanced undergraduates and to graduate students. Since it gives a survey on the study of communication complexity and formulates a lot of research problems we expect it will also prove to be a reference for researchers in this area.
First of all I would like to thank Grzegorz Rozenberg and Atto Salomaa, who encouraged me to write this book, and to Burkhard Monien and Wolfgang Thomas for the good working atmosphere in Paderborn and Kiel during the work on the book. I am indebted to Ingeborg Mayer, Andrew Ross and Hans Wossner of Springer-Verlag for their editorial help, comments and suggestions which essentially contributed to the quality of the presentation of the book.
I am grateful for the comments and materials received from several people, including Ivana Cerna, Josef Gruska, Ivana HSltring, Oliver Matz, Dana Par- dubska, Anna Slobodova, Ondrej Sykora, Imrich Vrto, Juraj Waczulik, and Avi Wigderson. Special thanks go to Martin Dietzfelbinger and Georg Schnitger for an intensive research cooperation, which during the work on the book led to the solutions of some open problems enabling to present a complete picture of some research directions on communication complexity in this book. I would like to thank Sebastian Seibert for carefully reading of the whole manuscript. I am indebted to Heidi Luca-Gottschalk, Oliver Matz, Walter Unger, and Thomas Wilke for the help with LaTeX and to Marion Kiipper and Gerti Rosenfeld for typing some parts of the manuscript.
My deepest thanks go to Tanja, not only for carefully typing of several parts of this book.
Kiel, January 1997 Juraj Hromkovic
The study of communication complexity becomes a well-defined indepen- dent area of complexity theory. In addition to a strong relation to several funda- mental complexity measures (and so to several fundamental problems of com- plexity theory) communication complexity has contributed to the study and to the understanding of the nature of determinism, nondeterminism, and random- ness in algorithmics. There already exists a non-trivial mathematical machinery to handle the communication complexity of concrete computing problems, which gives a hope that the approach based on communication complexity will be in- strumental in the study of several central open problems of recent complexity theory.
This book presents the basic concepts in the study of communication com-plexity and in its application in proving lower bounds on distinct fundamental complexity measures. In the applications we focus on the complexity measures of realistic, parallel computing models like combinational (Boolean) circuits, VLSI circuits and interconnection networks. The book is written at a level ac- cessible to advanced undergraduates and to graduate students. Since it gives a survey on the study of communication complexity and formulates a lot of research problems we expect it will also prove to be a reference for researchers in this area.
First of all I would like to thank Grzegorz Rozenberg and Atto Salomaa, who encouraged me to write this book, and to Burkhard Monien and Wolfgang Thomas for the good working atmosphere in Paderborn and Kiel during the work on the book. I am indebted to Ingeborg Mayer, Andrew Ross and Hans Wossner of Springer-Verlag for their editorial help, comments and suggestions which essentially contributed to the quality of the presentation of the book.
I am grateful for the comments and materials received from several people, including Ivana Cerna, Josef Gruska, Ivana HSltring, Oliver Matz, Dana Par- dubska, Anna Slobodova, Ondrej Sykora, Imrich Vrto, Juraj Waczulik, and Avi Wigderson. Special thanks go to Martin Dietzfelbinger and Georg Schnitger for an intensive research cooperation, which during the work on the book led to the solutions of some open problems enabling to present a complete picture of some research directions on communication complexity in this book. I would like to thank Sebastian Seibert for carefully reading of the whole manuscript. I am indebted to Heidi Luca-Gottschalk, Oliver Matz, Walter Unger, and Thomas Wilke for the help with LaTeX and to Marion Kiipper and Gerti Rosenfeld for typing some parts of the manuscript.
My deepest thanks go to Tanja, not only for carefully typing of several parts of this book.
Kiel, January 1997 Juraj Hromkovic
加载中...