Class Description

Φ2P: 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 Σ2P and Π2P.

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

Linked From

No class.