-1
$\begingroup$

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.
Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – Raphael ♦
    Nov 2, 2018 at 13:48
  • $\begingroup$ 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! $\endgroup$
    – Raphael ♦
    Nov 2, 2018 at 13:49
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Nov 5, 2018 at 3:56

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

One example is graph isomorphism.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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