摘要：We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P3-partition of the graph G. A necessary condition (*) has been found and two classes of graphs have been identified where the search problem of finding a feasible P3- partition is polynomially solvable and, in addition, (*) is not only necessary but also sufficient for the existence of a P3-partition. It is shown further that the decision problem on two particular graph classes - defined in terms of forbidden subgraphs - remains NP- complete, but is polynomially solvable on the intersection of those two classes. Moreover, for every natural number m, a stabilizing structure with Single Input m-Output controllers can be found in polynomial time for the system in question, if it admits one.
