S2P (complexity)

In computational complexity theory, S^P
₂ is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language L is in ${\displaystyle {\mathsf {S}}_{2}^{P}}$ if there exists a polynomial-time predicate P such that

• If ${\displaystyle x\in L}$, then there exists a y such that for all z, ${\displaystyle P(x,y,z)=1}$,
• If ${\displaystyle x\notin L}$, then there exists a z such that for all y, ${\displaystyle P(x,y,z)=0}$,

where size of y and z must be polynomial of x.