2
$\begingroup$

I'm a bit confused about the PH. I know that the class $NP^{NP}$ is the class of problems that can be verified in polynomial time if we have access to an NP oracle. I'm wondering, what is the complexity class $NP^{P^{NP}}$? Is it the same as $NP^{NP}$ (i.e., the second level of PH) or $NP^{NP^{NP}}$ (i.e., the third level of PH)? Basically, will the $P^{NP}$ oracle bring more power?

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

A nondeterminisitic poly-time machine can itself simulate calls to a deterministic poly-time subprocedure (possibly with oracle), thus $$\mathsf{NP^{P^{\mathit X}}=NP^{\mathit X}}$$ for any oracle $X$. In particular, $$\mathsf{NP^{P^{NP}}=NP^{NP}}.$$

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.