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?
$\begingroup$
$\endgroup$
1
-
$\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$– RaphaelCommented Nov 19, 2015 at 20:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
For deterministic reductions,
$$\big\{\langle L,U,N \rangle : N \text{ has a factor in } \{L,L+1,\ldots,U-1,U\}\big\}$$
(This answer is enough to make the zero-error reduction effective.)
