Are there problems known to be not in $P$ but not known to be outside $NP$?

Question

Although most experts believe that $NP$ is not equal to $P$, for a long time I believed that of the two directions of attacking the $P$ vs $NP$ problem trying to prove that $P = NP$ is the more fun one as it can be resolved by finding a clever algorithm, while showing $P \neq NP$ requires some abstract reasoning to show that certain problems cannot possibly be solved by any polynomial time algorithm.

Today it dawned on me however that other people have already done the abstract reasoning showing some problems outside $P$ and hence one actually might be able to show that $P \neq NP$ (provided it's true) by constructing an algorithm. Just take one of the known 'non-$P$' problems and show that it is in $NP$ by cooking up a certificate for it as well as an polynomial time algorithm that verifies it.

Although I have no plans of wasting my time carrying out this scheme, I am curious if there are any known problems for which one might try it. That is: are there any problems known not to be in $P$ but not known to be outside $NP$?

http://www.icm2014.org/en/awards/prizes/NevanlinnaPrizeWinner — Will Jagy, Nov 04 '14 at 21:24
Thanks for the link! I can't play sound now so I'll have to play the video later, but I looked up the unique games conjecture on Wikipedia. What is not clear to me: do you mean that some (or all?) problems about which the UGC states that they are NP hard are examples of the type of problem I am asking for in the question? Or perhaps that UCG would imply that under assumption of P != NP? — Vincent, Nov 04 '14 at 22:01
Just that, in the absence of a resolution of P vs. NP, there is progress on this. — Will Jagy, Nov 04 '14 at 22:04

score 2 · Accepted Answer · 2015-05-31T23:57:10.127

2

Yes. $\:$ The EXPTIME-complete problems are such problems.

More generally, for every time-constructible function f in $\:$n^$(\omega(1))$ $\cap$ 2^(n^(O(1)))$\:$, $\:$ the problem "Does the Turing machine M halt within f(number_of_states_in_(M)) steps?"
is not in P but not known to be outside NP.

edited May 31 '15 at 23:57

answered May 31 '15 at 23:50

According to the page you linked these are known to be outside $NP$ and thus don't answer the question. – ruler501 May 31 '15 at 23:55
Where does it claim that? $;$ – May 31 '15 at 23:57
nevermind I read it wrong, it says the $NEXPTIME$ complete problems are not in $NP$, my apologies. – ruler501 Jun 01 '15 at 00:00

Are there problems known to be not in $P$ but not known to be outside $NP$?

1 Answers1