On the Cost of Deciding Consensus

Details On the Cost of Deciding Consensus On the Cost of Deciding Consensus

2012-02-14

arxiv.org/abs/1202.3167v1

Mathematics

Optimization and Control

Scientific paper

We study the computational complexity of a general consensus problem for switched systems. A set of n by n stochastic matrices {P_1, ..., P_k} is a consensus set if for every switching map tau from N to {1, ..., k} and for every initial state x(0), the sequence of states defined by x(t+1)=P_{tau(t)} x(t) converges to a state whose entries are all identical. We show in this paper that, unless P=NP, the problem of determining if a set of matrices is a consensus set cannot be decided in polynomial-time. As a consequence, unless P=NP, it is not possible to give efficiently checkable necessary and sufficient conditions for consensus. This provides a possible explanation for the absence of such conditions in the current literature on consensus. On the positive side, we provide a simple algorithm which checks whether {P_1, ...,P_k} is a consensus set in O(Bkn^2+k^{2^{2n}} n^3) operations where B is the number of bits needed to specify each entry of P_1, ..., P_k.

Affiliated with

Also associated with

No associations

Rating

On the Cost of Deciding Consensus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Cost of Deciding Consensus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Cost of Deciding Consensus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556006