In the computational complexity theory, the low hierarchy and high hierarchy of complexity levels were introduced in 1983 by Uwe Schöning to describe the internal structure of the complexity class NP. The low hierarchy starts from complexity class P and grows "upwards", while the high hierarchy starts from class NP and grows "downwards".
Later these hierarchies were extended to sets outside NP.
The framework of high/low hierarchies makes sense only under the assumption that P is not NP. On the other hand, if the low hierarchy consists of at least two levels, then P is not NP.
It is not known whether these hierarchies cover all NP.
Famous quotes containing the word high:
“It is marvelous indeed to watch on television the rings of Saturn close; and to speculate on what we may yet find at galaxy’s edge. But in the process, we have lost the human element; not to mention the high hope of those quaint days when flight would create “one world.” Instead of one world, we have “star wars,” and a future in which dumb dented human toys will drift mindlessly about the cosmos long after our small planet’s dead.”
—Gore Vidal (b. 1925)