Intermediate $\mathsf{NP}$-complete problems? Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete problem even if input integers are bounded by a polynomial.


  Assuming, $\mathsf{P \ne NP}$, Can we prove that intermediate NP-complete problems must exist? If the answer is yes, Is there such "natural" candidate problem?


Here, Intermediate NP-complete problem is a problem that neither has a pseudo-polynomial time algorithm nor NP-complete in the strong sense.  

I guess that there is an infinite hierarchy of intermediate NP-complete problems between weak NP-completeness and strong NP-completeness.

EDIT March 6th: As mentioned in the comments, an alternative way to pose the question is:


  Assuming, $\mathsf{P \ne NP}$, Can we prove the existence of NP-complete problems that neither have polynomial time algorithm nor NP-complete when the numerical
  inputs are presented in unary? If the answer is yes, Is there such "natural" candidate problem?


EDIT2 March 6: The reverse direction of the implication is true. The existence of such "intermediate" $NP$-complete problems implies $\mathsf{P \ne NP}$ since if $\mathsf{ P=NP}$ then unary $NP$-complete problems are in $P$.
This is a partial answer that only gives a candidate intermediate $NP$-complete problem.

$k$-Equal Sum Subsets problem: Given a multiset of $n$ positive integers $A = \{a_1,...,a_n\}$, are there $k$ nonempty disjoint subsets $S_1,...,S_k ⊆ \{a_1,...,a_n\}$ such that $sum(S_1) = ... = sum(S_k)$?

The problem is weakly $NP$-complete when $k= O(1)$ and therefore has pseudo-polynomial time algorithm for any fixed constant integer $k &gt; 2$. However, it becomes strongly $NP$-complete when the number of equal sum subsets $k= \Omega(n)$.

If $k= \omega(1)$ and $k= O(\log n)$ then $k$-Equal Sum Subsets problem is a candidate intermediate $NP$-complete problem (as described in the question). This problem is neither known to have a pseudo-polynomial time algorithm nor proven to be $NP$-complete in the strong sense.

Reference:

CIELIEBAK, EIDENBENZ, PAGOURTZIS, and SCHLUDE, ON THE COMPLEXITY OF VARIATIONS OF EQUAL SUM SUBSETS, Nordic Journal of Computing 14(2008), 151–172