13

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • I think putting a restriction on the value of the numbers in Partition should do it. – Kaveh Mar 01 '13 at 16:21
  • Just a clarification (I'm not an expert): does the definition of strong/weak NP-completeness allow intermediate degrees? I.e. doesn't "strongly NPC" means "not weakly NPC" and vice versa? – Marzio De Biasi Mar 01 '13 at 16:36
  • similar to ladner's thm which states [iiuc] that if P$\neq$NP then NP hard problems (then superpolynomial time) must exist that are not NP complete (the so-called NPI, NP-intermediate class?). however something seems wrong with question. NPI is a defined class & its not nec the same as NP complete right? so an "intermediate NP complete" problem does not seem to make sense directly.... – vzn Mar 01 '13 at 17:41
  • 2
    @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 01 '13 at 17:46
  • 4
    @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 02 '13 at 06:16
  • NPI/ladners thm, wikipedia sorry, stated it wrong, its a little subtle and predicated on the P=?NP conjecture. try again: NPI problems exist and are weaker than NP hard/NP complete and harder than P if P$\neq$NP? anyway suggest Mohammeds use of the word "intermediate" wrt NP/NP complete is problematic & inconsistent because NPI has already been defined. – vzn Mar 02 '13 at 15:04
  • 2
    @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 02 '13 at 20:39
  • 2
    @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 06 '13 at 00:43
  • 1
    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

1 Answers1

2

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149