Accession Number : ADA137443

Title :   On the Complexity of Distributed Decision Problems,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s) : Tsitsiklis,J ; Athans,M

PDF Url : ADA137443

Report Date : Nov 1983

Pagination or Media Count : 6

Abstract : This document studies the computational complexity of finite versions of the simplest and fundamental problems of distributed decision making and it is shown that, apart from a few exceptions, such problems are hard (NP-complete, or worse). Some of the problems studied are the well-known team decision problem, the distributed hypothesis testing problem, as well as the problem of designing a communications protocol that guarantees the attainment of a prespecified goal with as little communications as possible. These results indicate the inherent difficulty of distributed decision making, even for very simple problems, with trivial centralized counterparts and suggest that optimality may be an elusive goal of distributed systems.

Descriptors :   *Decision making, *Decentralization, *Computations, Information theory, Problem solving, Communication and radio systems, Hypotheses, Probability

Subject Categories : Statistics and Probability
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE