Class Description

S₂E: Second Level of the Symmetric Linear Exponent Hierarchy

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

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

Linked From

No class.