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

Improve this question
$\endgroup$
9
  • 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 13:02

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.