Title :
Control problems and the polynomial time hierarchy
Author :
Tierno, Jorge E. ; Doyle, John C.
Author_Institution :
Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA, USA
Abstract :
Classifies control problems by exhibiting their alternating quantifier structure. This classification allows the authors to relate these control problems to the computational complexity classes of the polynomial time hierarchy. A specific synthesis problem for uncertain systems is shown to be hard in the class Π2p
Keywords :
computational complexity; control system analysis; control system synthesis; uncertain systems; alternating quantifier structure; computational complexity classes; control problems; polynomial time hierarchy; synthesis problem; uncertain systems; Computational complexity; Control system analysis; Control system synthesis; Control systems; NP-complete problem; Polynomials; Sensor systems; Uncertain systems; Uncertainty;
Conference_Titel :
Decision and Control, 1995., Proceedings of the 34th IEEE Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-7803-2685-7
DOI :
10.1109/CDC.1995.478587
