Class Description

Φ₂P: Second Level of the Symmetric Hierarchy, Alternative Definition

The class of problems for which there exists a polynomial-time predicate P(x,y,z) such that for all x, if the answer on input x is "yes," then

1. For all y, there exists a z for which P(x,y,z).
2. For all z, there exists a y for which P(x,y,z).

Contained in Σ₂P and Π₂P.

Defined in [Can96], where it was also observed that Φ₂P = S₂P.

Linked From 0 Classes

No class.