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

• @MarzioDeBiasi There is another definition of strong NP-completeness (may be less popular one) which defines a number problem to be NP-complete even if all input integers are represented in unary notation. – Mohammad Al-Turkistany Mar 1 '13 at 17:46
• @vzn this is a ridiculous comment! 1) ladner's thm is not about np hard problems that are not np complete; 2) while Mohammad is sort of overloading terminology, he defines his class of problems clearly (NPC, not strongly NPC and no pseudopoly time algorithm) and it is different from NPC. – Sasho Nikolov Mar 2 '13 at 6:16
• @MohammadAl-Turkistany: ok thanks, perhaps I suggest you to call it unary NP-completeness like in Garey and Johnson "Strong" NP-Completeness Results: Motivation, Examples, and Implications. So you are searching intermediate problems between unary NPC and pseudopolynomial NPC. I'm still trying to grasp it, however, in their paper, G&J say (about unary NPC): " ... It is not hard to see that this corresponds to our notion of strong NP-completeness ...". – Marzio De Biasi Mar 2 '13 at 20:39
• @MarzioDeBiasi I think the idea is that we can (->) given a binary number of size polynomial in the input, convert it to unary in polytime and run the unary algorithm, (<-) given a unary input of length poly in the rest of the input, read the whole thing and convert it to binary and run the binary algorithm. – usul Mar 6 '13 at 0:43
• Since any problem that has a polynomial-time algorithm if one of the input parameters is fixed is in FPT, you seem to be essentially asking whether there are problems harder than FPT but not W[1]-hard. As far as I know Ladner's theorem can be extended to this setting; it might be in the Flum/Grohe textbook. – András Salamon Jun 16 '13 at 13:02

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