# The most subtle NP-“intermediate” problem

What is the $$NP$$ problem whose status in $$P$$ or $$NP$$-complete is still unsettled, as of 2018?

This question is inspired by the following two recent breakthroughs:

1. The work of Mulzer et. al on $$NP$$-completeness of min-weight triangulation.
2. Recent quasi-polynomial algorithm of Babai for graph isomorphism. The link is to Helfgott's more recent (2017) paper.
• a) There are probably several. b) Which research have you done yourself? c) I doubt the long-term use of answers that, by definition, are outdated soon. – Raphael Nov 2 '18 at 13:48
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Nov 2 '18 at 13:49
• I don't understand what this question is asking. It says "the NP problem..." but there are multiple such NP problems. If you are asking for all NP problems, this is too broad. The title suggests you want the "most subtle" such problem, but it's not clear how you to define most subtle, so that seems either too vague/unclear or subjective. – D.W. Nov 5 '18 at 3:56

In addition to Eugen's answer, the problem of determining whether an integer $$N$$ has a factor less or equal to $$M$$ is also not known to be in either P or NP-C.
IMHO, there are dozens of meaningful $$NP$$ problems which statuses have not been dichotomized.
In fact, each one of your rather long list of "Karp hardness of..." questions contains an $$NP$$ problem that has some such variant. As long as one delves deep enough into each of these, one would find some subtle variant for oneself.