1
$\begingroup$

These would be problems known to be in exp where there could hypothetically be a P or NP algorithm, but none have been discovered yet if one is possible.

$\endgroup$
3
  • $\begingroup$ The title doesn't match the body. "not known to be in NP" is different from "there could hypothetically be a polynomial time algorithm, but none have been discovered yet if one is possible". Please put the question in the body of the post. The title should be a short summary. $\endgroup$
    – D.W.
    Jan 7 at 22:07
  • $\begingroup$ @ D.W.♦ I fixed it. $\endgroup$ Jan 7 at 22:13
  • $\begingroup$ cstheory.stackexchange.com/q/799/5038 $\endgroup$
    – D.W.
    Jan 7 at 22:44
2
$\begingroup$

Assuming that $NP\not= PSPACE$ and $PSPACE \not= EXPTIME$, all $PSPACE$-complete problems are incomplete in $EXPTIME$

$\endgroup$
3
$\begingroup$

Any BQP-complete problem should suffice, since BQP is contained in EXPTIME but not believed to be contained in NP and not believed to be equal to EXPTIME.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.