<p>I would say the answer is clearly no (that is, no one knows), because no one knows whether the NP-complete problems can be solved in <em>polynomial</em> time, let alone <em>pseudo</em>-polynomial time. (Every polynomial algorithm is, of course, pseudopolynomial.) If you can find a problem in NPC that cannot be solved in pseudopolynomial time, you have just proven that P≠NP, so I think it’s safe to say that no such examples will be produced any time soon.</p>

CC BY-SA 3.0
2011-07-15T09:42:17.750Z
I've edited my question to "Does anyone know some candidate problems ... ?"
Oleksandr Bondarenko
CC BY-SA 3.0
2011-07-15T08:57:10.043Z
2011-07-15T08:57:10.043Z
Magnus Lie Hetland
<p>I do not know if you are interested in hearing more detail of my comment on your question, but here is more detail anyway.</p>

<p>If P=NP, every problem in NP can be solved in polynomial time and therefore in pseudo-polynomial time, which means that no problem satisfies your requirement, as Magnus noted in his answer.  So assume P≠NP in the rest of this answer.</p>

<p>Because P≠NP, there exists a language <i>L</i>∈NP∖P which is not NP-complete (Ladner’s theorem).  Consider the following problem:</p>

<p><strong>Direct product of Partition and <i>L</i></strong><br>
<em>Instance</em>: <i>m</i> positive integers <i>a</i><sub>1</sub>, …, <i>a</i><sub><i>m</i></sub> and <i>k</i> integers <i>b</i><sub>1</sub>, …, <i>b</i><sub><i>k</i></sub>∈{0,1}.<br>
<em>Question</em>: Do both of the following hold?<br>
(1) The <i>m</i> integers <i>a</i><sub>1</sub>, …, <i>a</i><sub><i>m</i></sub> form a yes-instance of the Partition problem.<br>
(2) The <i>k</i>-bit string <i>b</i><sub>1</sub>…<i>b</i><sub><i>k</i></sub> belongs to <i>L</i>.</p>

<p>Following the paper by Garey and Johnson, define the Length function as <i>m</i>+⌈log max<sub><i>i</i></sub> <i>a</i><sub><i>i</i></sub>⌉+<i>k</i> and the Max function as max<sub><i>i</i></sub> <i>a</i><sub><i>i</i></sub>.</p>

<p>It is a routine to check (i) that it is NP-complete in the weak sense, (ii) that it does not have a pseudo-polynomial-time algorithm, and (iii) that it is not NP-complete in the strong sense.</p>

<p>(Hints: (i) Membership to NP follows from the fact that both the Partition problem and <i>L</i> are in NP.  For NP-hardness, reduce Partition to this problem.  (ii) Construct a pseudo-polynomial transformation from <i>L</i> to this problem.  (iii) Construct a pseudo-polynomial transformation from this problem to <i>L</i> by using the fact that Partition has a pseudo-polynomial-time algorithm.)</p>

<p>There is nothing special about the Partition problem in this construction: you can use your favorite weakly NP-complete problem with a pseudo-polynomial-time algorithm.</p>

CC BY-SA 3.0
2011-07-18T13:26:20.353Z
Thank you for the answer. I was more interested in non-artificial problems contrary to the one described by you. Though I'm in doubt concerning the definition of a non-artificial problem.
Oleksandr Bondarenko
CC BY-SA 3.0
2011-07-18T13:56:23.863Z
@Oleksandr: As for the choice of L, you can use any NP-intermediate language.  However, you are right that no matter which language L you choose, this construction gives an artificial problem because of taking the direct product with Partition.  I do not know of any natural problem satisfying your requirement.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-18T14:02:55.157Z
Anyway, your answer is interesting for me and deserves upvote.
Oleksandr Bondarenko
CC BY-SA 3.0
2011-07-19T15:04:45.587Z
(Edit: Nevermind. :))
Daniel Apon
CC BY-SA 3.0
2011-07-18T12:27:09.710Z
2011-11-23T17:50:25.333Z
2011-11-23T17:50:25.333Z
Tsuyoshi Ito
<p>In their <a href="http://www.cs.unc.edu/~plaisted/comp750/Strong-NP-completness.pdf">paper</a> (p. 503) Garey and Johnson remark:</p>

<blockquote>
  <p>... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ...</p>
</blockquote>

<p>Does anyone know some candidate problems with the properties the mentioned above?</p>

<p><em>I think the possible answer to this question can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.</em></p>

CC BY-SA 3.0
2011-07-14T18:49:13.733Z
Isn’t it possible to make up an artificial example by combining an NP-complete problem with a pseudo-polynomial time algorithm and an NP-intermediate language from Ladner’s theorem?
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-18T04:12:36.820Z
My answer posted earlier was incorrect; my apologies. This is what happens when I hand-wave and post!
Daniel Apon
<ds.algorithms><np-hardness><np>
Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?
Oleksandr Bondarenko
# Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

(Asked by: username_0 on 2011-07-14)

In their [paper](http://www.cs.unc.edu/~plaisted/comp750/Strong-NP-completness.pdf) (p. 503) Garey and Johnson remark:

> ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ...

Does anyone know some candidate problems with the properties the mentioned above?

*I think the possible answer to this question can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.*

**Tags:** ds.algorithms, np-hardness, np

> **Comments:**
> **username_1**: Isn’t it possible to make up an artificial example by combining an NP-complete problem with a pseudo-polynomial time algorithm and an NP-intermediate language from Ladner’s theorem?  
> **username_2**: My answer posted earlier was incorrect; my apologies. This is what happens when I hand-wave and post!  

---

## 2 answers

### Answer by username_1 on 2011-07-18. Score: 17 | Accepted answer

I do not know if you are interested in hearing more detail of my comment on your question, but here is more detail anyway.

If P=NP, every problem in NP can be solved in polynomial time and therefore in pseudo-polynomial time, which means that no problem satisfies your requirement, as Magnus noted in his answer. So assume P≠NP in the rest of this answer.

Because P≠NP, there exists a language *L*∈NP∖P which is not NP-complete (Ladner’s theorem). Consider the following problem:

**Direct product of Partition and *L***  
*Instance*: *m* positive integers *a*1, …, *a**m* and *k* integers *b*1, …, *b**k*∈{0,1}.  
*Question*: Do both of the following hold?  
(1) The *m* integers *a*1, …, *a**m* form a yes-instance of the Partition problem.  
(2) The *k*-bit string *b*1…*b**k* belongs to *L*.

Following the paper by Garey and Johnson, define the Length function as *m*+⌈log max*i* *a**i*⌉+*k* and the Max function as max*i* *a**i*.

It is a routine to check (i) that it is NP-complete in the weak sense, (ii) that it does not have a pseudo-polynomial-time algorithm, and (iii) that it is not NP-complete in the strong sense.

(Hints: (i) Membership to NP follows from the fact that both the Partition problem and *L* are in NP. For NP-hardness, reduce Partition to this problem. (ii) Construct a pseudo-polynomial transformation from *L* to this problem. (iii) Construct a pseudo-polynomial transformation from this problem to *L* by using the fact that Partition has a pseudo-polynomial-time algorithm.)

There is nothing special about the Partition problem in this construction: you can use your favorite weakly NP-complete problem with a pseudo-polynomial-time algorithm.

> **Comments:**
> **username_0**: Thank you for the answer. I was more interested in non-artificial problems contrary to the one described by you. Though I'm in doubt concerning the definition of a non-artificial problem.  
> **username_1**: @Oleksandr: As for the choice of L, you can use any NP-intermediate language.  However, you are right that no matter which language L you choose, this construction gives an artificial problem because of taking the direct product with Partition.  I do not know of any natural problem satisfying your requirement.  
> **username_0**: Anyway, your answer is interesting for me and deserves upvote.  
> **username_2**: (Edit: Nevermind. :))  

---

### Answer by username_3 on 2011-07-15. Score: 1

I would say the answer is clearly no (that is, no one knows), because no one knows whether the NP-complete problems can be solved in *polynomial* time, let alone *pseudo*-polynomial time. (Every polynomial algorithm is, of course, pseudopolynomial.) If you can find a problem in NPC that cannot be solved in pseudopolynomial time, you have just proven that P≠NP, so I think it’s safe to say that no such examples will be produced any time soon.

> **Comments:**
> **username_0**: I've edited my question to "Does anyone know some candidate problems ... ?"  

---

