Communication complexity
The communication complexity is a branch of complexity theory and is applied to examine the question of how much communication to solve specific tasks is necessary, the input is distributed over several computers. The main focus is on the number of bits that must be sent between the computers so that they can fulfill their task at hand. The communication complexity is a tool of theoretical computer science, especially in the proof of lower bounds for the resource requirements of calculations.
Demarcation to complexity theory
The goal of complexity theory is to estimate the minimum resources for solving algorithmic problems. The previously proven lower bounds based on complexity theoretic hypotheses or relate to specific scenarios such as the black-box scenario.
The core ideas used to prove these lower bounds in 1979 filtered out and separated from Andrew C. Yao of the original concrete application of complexity theory. This led to the theory of communication complexity. First introduced as a cost measure for data exchange in parallel computers, the communication complexity presented subsequently out as an important tool for deriving lower bounds in the VLSI chip design and the circuit complexity.
Aspects and basic principle
In the electronic data processing many aspects to be considered as a sequence of communication processes. A communication always takes place or is always necessary when two or more computers, components, systems or people must work together to solve a problem that can handle any of them alone, perhaps because no one has alone over the entire data or resources. In many cases, there is an obvious communication such as eg. when information is sought from the Internet. It requests and responses over an Internet connection will be taught.
However, it is also possible scenarios in which communication takes place only implicitly, such as eg. by use of a computer program. In this case, the communication and the exchange of information between different computer components is performed.
Communication Model
The calculation of a function on a VLSI chip, the given chip area into two areas. Thus, each region receives a portion of the input. Thus a calculation of the function can be performed, the two regions of the chip need to exchange information. When the function to be calculated needs to be replaced much information because of the characteristics, either requires a lot of computing time or the boundary line between the two regions of the chip and therefore the chip itself should be large.
Communication complexity is the number of bits that two processors (we call them Alice and Bob) must exchange to jointly evaluate a function when each processor initially knows one of the arguments or.
Alice is known only from the input, while Bob knows. Both are given internally unlimited computing capacity. The only significant issue is the communication. Alice and Bob agree beforehand on a protocol that prescribes for every situation, what to do.
If the result of the previously communicated bits, then knows Alice and Bob. Both must now be clear who sends the next message, the sent message must depend only on local information. At the end of communication, Alice and Bob should know. The length of the protocol, for the input, the number of bits that are communicated between Alice and Bob. The number of bits sent for computing is regarded as the communication complexity of the protocol on input.
The communication complexity of a function is the length of the shortest protocol.
AT ² barriers on a VLSI - chip
The chip design is now as then determines which accommodate as much logic on a small chip, this reduces the cost. On the other hand, the chip quickly compute a result. VLSI designers were therefore lower bounds in terms of calculation time and the size of the chips of great interest. As was for the discrete Fourier transform, for example, be proved that AT ² > n2 16. Herein, the surface of the chip, the required clock cycles and the length of the binary input. By this calculation to obtain the so-called AT ² barriers.
AT ² barriers are not only limited to the VLSI design but can also be used for thousands of other functional calculations.