# Conjectured NP-complete problems

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?

• I would guess that all problems for which neither membership in P nor in NPC is known would be conjectured to be in NPI. Commented Nov 19, 2015 at 20:31

## 2 Answers

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.

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.)