交互复杂度--面向网络计算的复杂度指标

随着网络计算的盛行,计算问题的解决越来越倾向于通过分布在网络上的服务的交互来完成,研究问题在交互意义上的复杂度显得日益重要．提出了以交互为基本要素的通用计算模型——交互积,在此基础上提出了算法的交互复杂度指标,并初步探索了交互复杂度和时间复杂度之间的关系．利用3-GIP的通用性,可以降低网格系统的成本和提高好用性,而交互复杂度可以作为网格上问题解决方案的评价指标,从而可以指导网格应用的开发．

Interaction Complexity-A Complexity Measure for Network-Based Computing

With the development of network-based computing, computational problem-solving tends to be cooperatively carried out by distributed services.On this ground, how many times of interaction must be involved is decisive for the problem-solving efficiency, which calls for research on interaction-related complexity of a problem.Hence, a computation model, named interaction product, is proposed to replace Turing machines with the universal computation model.Interaction product consists of some automata interacting by accessing their shared cells, and its universality helps to realize the low cost and high accessibility of grids. Interaction complexity is defined based on this model since it explicitly describes interaction, and it differs from other interaction-related complexity in that it emphasizes interaction and at the same time strongly restricts the computational capability of the individuals.As an interaction-centric measure of problem-solving efficiency, interaction complexity helps to optimize grid applications.The relationship between interaction complexity and the classic time complexity is also discussed.