On the cost of deciding consensus

Vincent Blondel, Alex Olshevsky

Research output: Contribution to journalConference articlepeer-review


We study the computational complexity of a general consensus problem for switched systems. A set of n × n stochastic matrices {P 1,⋯, Pk} is a consensus set if for every switching map τ : → {1,⋯, k} and for every initial state x(0), the sequence of states defined by x(t + 1) = Pτ(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 {P1,⋯, P k} is a consensus set in a number of operations which scales as a doubly exponential in n.

Original languageEnglish (US)
Article number6427078
Pages (from-to)2213-2218
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
StatePublished - 2012
Externally publishedYes
Event51st IEEE Conference on Decision and Control, CDC 2012 - Maui, HI, United States
Duration: Dec 10 2012Dec 13 2012

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'On the cost of deciding consensus'. Together they form a unique fingerprint.

Cite this