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 -