Oracle for solving super-exponential problems?

Question

Suppose we can use an NP-complete oracle (in polynomial time).

Suppose we are solving a sequence of problems of super-exponentially increasing complexity. (We have plenty of time and space for the sake of the question.)

Question: How the NP-complete oracle can (or cannot) help us to solve the super-exponential?

Answer 1

Let $A$ be $\textsf{PSPACE}$-complete. Then $\textsf{NP}^{A} \subseteq \textsf{PSPACE} \subseteq \textsf{P}^{A}$.

The containment $\textsf{NP}^{A} \subseteq \textsf{PSPACE}$ follows from the following two facts:

• The certificate for the $\textsf{NP}^{A}$ machine must still be poly-sized.
• Each query the $\textsf{NP}^{A}$ machine makes must still have polynomial size, and the machine only makes polynomially many queries. Thus, a $\textsf{PSPACE}$ machine can simulate the oracle calls.

Now suppose $A$ is $\textsf{NP}$-complete. It is well known that $\textsf{NP}^{A} = \Sigma_{2}^{p}$, which is at the second level of the polynomial-time hierarchy and sits very far below $\textsf{EXPTIME} = \textsf{DTIME}(2^{\text{poly}(n)})$. Now $\textsf{P}^{A} = \Delta_{2}^{p} \subseteq \Pi_{2}^{p} \cap \Sigma_{2}^{p}$.