I have a $\text{NEXP}$-hard problem, that can be solved by a $\text{NEXP}^\text{NP}$ algorithm using a single oracle call. So from Hemaspaandra we know it is in $\text{P}^\text{NE}$, giving us $\text{NEXP}$-completeness under Cook-reductions.

  • Are there (more or less) natural problems complete for $\text{P}^\text{NE}$?
  • What do we know about the space between $\text{NEXP}$ and $\text{P}^\text{NE}$?
  • Anything else that might help to sharpen this result (to Karp-reductions)?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.