Low and high hierarchies
id:
low-and-high-hierarchies-201-14583226
title:
Low and high hierarchies
text:
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 o
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Low_and_high_hierarchies
date created:
date modified:
2023-08-15T23:00:34Z
main entity:
{"identifier":"Q6692967","url":"https://www.wikidata.org/entity/Q6692967"}
image:
fields total:
13
integrity:
13