Low (complexity)

An A machine can simulate many oracle queries to B without exceeding its resource bounds.

[3] Note that being self-low is a stronger condition than being closed under complement.

This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely because it implies that the polynomial hierarchy collapses to the first level, whereas it is widely believed that the hierarchy is infinite.

Some of the more complex and famous results regarding lowness of classes include: Lowness is particularly valuable in relativization arguments, where it can be used to establish that the power of a class does not change in the "relativized universe" where a particular oracle machine is available for free.

For example, in the relativized universe of BQP, PP is still closed under union and intersection.