Class Description

S2E: Second Level of the Symmetric Linear Exponent Hierarchy

Same as S2P, except that the predicate P may be exponential.

Requires near-maximal sized circuits (that is, size Ω(2n/n)) [Li23]. In fact, this holds for the more general class O2E (defined analogously to O2P).

Linked From

No class.