# complexity theory – Where does this Oracle Problem belong in the Polynomial Hierarchy?

Given a problem $$E_0$$ such that:

1. Any valid solution $$S_0$$ if there is any is of polynomial length.

2. Assuming we are able to guess the solution $$S_0$$, for it to be valid:

i. There are a fixed set of properties $${U_k}$$, and $$S_0$$ must satisfy each one of it. Each property is an NP-Complete problem in itself.

ii. There are a fixed set of properties $${V_l}$$, and $$S_0$$ must fail each one of it. Each property is an co-NP-Complete problem in itself.

The solution $$S_0$$ is valid iff all we are able to produce a certificate for properties in $${U_k}$$ and $${V_l}$$ for ‘pass’ and ‘fail’ respectively.

Query 1: Assuming we have access to both NP-Complete and co-NP-Complete oracle both for guessing the initial solution $$S_0$$ and as well as to verify the properties where does this problem belong in the complexity/polynomial hierarchy?

Query 2: Where does this problem belong as compared to PSPACE?

I dont have much background in oracles, thus I am not so sure.