<p>This is a partial answer that only gives a candidate intermediate $NP$-complete problem.</p>

<p>$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)$?</p>

<p>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)$.</p>

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

<p>Reference:</p>

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

CC BY-SA 3.0
2015-01-28T21:34:02.387Z
Have you seen this http://cstheory.stackexchange.com/a/7427/15637 ?
Thomas Kalinowski
CC BY-SA 3.0
2015-01-28T21:57:23.047Z
Yes. That answer provides  arguably an artificial problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-01-28T21:09:53.680Z
2015-01-28T21:24:29.820Z
2015-01-28T21:24:29.820Z
Mohammad Al-Turkistany
<p>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.</p>

<blockquote>
  <p><strong>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?</strong></p>
</blockquote>

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

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

<p><strong>EDIT March 6th</strong>: As mentioned in the comments, an alternative way to pose the question is:</p>

<blockquote>
  <p><strong>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?</strong></p>
</blockquote>

<p><strong>EDIT2 March 6</strong>: 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$.</p>

CC BY-SA 3.0
2013-03-01T16:21:43.300Z
I think putting a restriction on the value of the numbers in Partition should do it.
Kaveh
CC BY-SA 3.0
2013-03-01T16:36:41.777Z
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
CC BY-SA 3.0
2013-03-01T17:41:24.600Z
similar to [ladner's thm](http://oldblog.computationalcomplexity.org/media/ladner.pdf) 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
CC BY-SA 3.0
2013-03-01T17:46:41.187Z
@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
CC BY-SA 3.0
2013-03-02T06:16:27.970Z
@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
CC BY-SA 3.0
2013-03-02T15:04:49.457Z
[NPI/ladners thm, wikipedia](http://en.wikipedia.org/wiki/NP-intermediate) 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
CC BY-SA 3.0
2013-03-02T20:39:07.560Z
@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](http://cs.unc.edu/~plaisted/comp750/Strong-NP-completness.pdf). 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
CC BY-SA 3.0
2013-03-06T00:43:23.067Z
@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
CC BY-SA 3.0
2013-06-16T13:02:51.893Z
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
<cc.complexity-theory><np-hardness><partition-problem>
Intermediate $\mathsf{NP}$-complete problems?
Mohammad Al-Turkistany
# Intermediate $\mathsf{NP}$-complete problems?

(Asked by: username_0 on 2013-03-01)

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

**Tags:** cc.complexity-theory, np-hardness, partition-problem
> **Comments:**
> **username_1**: I think putting a restriction on the value of the numbers in Partition should do it.  
> **username_2**: 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?  
> **username_3**: similar to [ladner's thm](http://oldblog.computationalcomplexity.org/media/ladner.pdf) 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....  
> **username_0**: @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.  
> **username_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.  
> **username_3**: [NPI/ladners thm, wikipedia](http://en.wikipedia.org/wiki/NP-intermediate) 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.  
> **username_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](http://cs.unc.edu/~plaisted/comp750/Strong-NP-completness.pdf). 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 ...".  
> **username_5**: @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.  
> **username_6**: 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.  

---

## 1 answers

### Answer by username_0 on 2015-01-28. Score: 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

> **Comments:**
> **username_7**: Have you seen this http://cstheory.stackexchange.com/a/7427/15637 ?  
> **username_0**: Yes. That answer provides  arguably an artificial problem.  

---

