2
$\begingroup$

Assume P != NP. Then there are many examples of problems in NP that are known not to be NP-complete, like 2-SAT, and many that are conjectured not to be NP-complete, like factorization. However, are there any problems that are widely conjectured but not known to be NP-complete?

$\endgroup$
  • $\begingroup$ I would guess that all problems for which neither membership in P nor in NPC is known would be conjectured to be in NPI. $\endgroup$ – Raphael Nov 19 '15 at 20:31
4
$\begingroup$

There are no natural problems that I am aware of that have that property. There are two problems which are "close", however.

The Minimum Circuit Size Problem is, given a truth table of a boolean function $f$ and an integer $k$, is $f$ computed by a circuit of size at most $k$? Note $MCSP \in NP$, and it is widely expected that $MCSP$ is "hard"; however, it is not known that $MCSP$ is $NP$-complete, and while it is easy to conjecture that it might be, there is also some evidence that it is not.

The Unique Games Conjecture states that approximating the value of a certain combinatoric problem is $NP$-hard. This problem is not strictly in $NP$ because its decision version is a "promise problem". Nevertheless, the UGC is one of the premier open questions of computer science today and there is little consensus on whether it is true or not.

$\endgroup$
2
$\begingroup$

For deterministic reductions,

$$\big\{\langle L,U,N \rangle : N \text{ has a factor in } \{L,L+1,\ldots,U-1,U\}\big\}$$

is such a problem.

(This answer is enough to make the zero-error reduction effective.)

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