TY - JOUR

T1 - On the cost of deciding consensus

AU - Blondel, Vincent

AU - Olshevsky, Alex

N1 - Funding Information:
The 1980s saw the first chasm in terms of bipartisan support of the NEA. From the outset, President Reagan’s aides in the presidential transition team exhibited animosity to the NEA. While they did not advocate destroying the NEA, they revealed the president’s dislike of the arts (Andrews, 2017). Deepening tensions concerning the arts and the NEA were manifested and magnified in 1989. Two controversies stood out; Andres Serrano’s photo, Piss Christ, which depicted Christ on the crucifix soaked in the artist’s urine, debuted quietly at a New York event in 1987. However, when it was shown in Virginia two years later, it was subject to withering attacks from conservative politicians when the Rev. Donald Wildmon, a leader of the conservative American Family Foundation of Tupelo (Mississippi), held a press conference and directed concerns to the National Council on the Arts (Andrews, 2017). That the work received financial support from the NEA—amounting to $15,000— caused the agency to become political fodder against which conservative politicians railed. Criticized for blasphemy, the work enraged the likes of Senate leader Jesse Helms of North Carolina; Senator D’Amato of New York called it “a deplorable, despicable display of vulgarity” (requoted in Andrews, 2017). Representative Dick Armey of Texas sent a threating letter to the, then, NEA acting chair, Hugh Southern, and urged him to cut the NEA’s ties to the artist for the “morally reprehensible trash” (requoted in Koch, 1998).

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84874261646&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874261646&partnerID=8YFLogxK

U2 - 10.1109/CDC.2012.6427078

DO - 10.1109/CDC.2012.6427078

M3 - Conference article

AN - SCOPUS:84874261646

SN - 0191-2216

SP - 2213

EP - 2218

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

M1 - 6427078

T2 - 51st IEEE Conference on Decision and Control, CDC 2012

Y2 - 10 December 2012 through 13 December 2012

ER -