13
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Mar 1 '13 at 17:46
  • 4
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Mar 2 '13 at 6:16
  • 2
    $\begingroup$ @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 ...". $\endgroup$ – Marzio De Biasi Mar 2 '13 at 20:39
  • 2
    $\begingroup$ @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. $\endgroup$ – usul Mar 6 '13 at 0:43
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon Jun 16 '13 at 13:02
2
$\begingroup$

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.

Reference:

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

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