-2
$\begingroup$

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

This question is inspored 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.
$\endgroup$
  • 1
    $\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 '18 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 '18 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 '18 at 3:56
1
$\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.

$\endgroup$
0
$\begingroup$

One example is graph isomorphism.

$\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.

$\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.