Stability of Time-Delay Systems (Gu KeQin)

时滞系统稳定性必备书That every problem in NP can be polynomially reduced to an NP-hard problem suggests a proof for NP-hardness. It follows that if a problem ℘1 is NP-hard and polynomially reducible to some problem ℘2, then ℘2 must also be NP-hard. In other words, if one is to prove that ℘2 is NP- hard, one may attempt to reduce polynomially a known NP-hard problem ℘1 to ℘2. In particular, it suffices to polynomially reduce ℘1 to just one instance of ℘2, since that particular instance of ℘2 is as difficult as any instance of ℘1, and therefore in the worst case, ℘2 must be as difficult as ℘1. A vast number of NP-hard and NP-complete problems have been discovered in this manner, among them notably are such classical problems as the satisÞability problem and the traveling salesman problem. The same strategy is adopted in our proof of the NP-hardness of the stability problem