We investigate the computational complexity of the

Our main result is a one-round interactive proof for the complement of BI, where the Verifier has access to an NP oracle. To obtain this, we use a recent result from learning theory by Bshouty et.al. that Boolean formulas can be learned probabilistically with equivalence queries and access to an NP oracle. As a consequence, BI cannot be complete for the second level of the Polynomial Hierarchy unless the Polynomial Hierarchy collapses. This solves an open problem posed by Borchert, Ranjan, and Stephan.

Further properties of BI are shown:
BI has And- and Or-functions,
the counting version of BI can be computed in polynomial time relative to BI,
and BI is self-reducible.