Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

In their paper (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.

• 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? Commented Jul 14, 2011 at 18:49
• My answer posted earlier was incorrect; my apologies. This is what happens when I hand-wave and post! Commented Jul 18, 2011 at 4:12

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 a1, …, am and k integers b1, …, bk∈{0,1}.
Question: Do both of the following hold?
(1) The m integers a1, …, am form a yes-instance of the Partition problem.
(2) The k-bit string b1bk belongs to L.

Following the paper by Garey and Johnson, define the Length function as m+⌈log maxi ai⌉+k and the Max function as maxi ai.

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.

• 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. Commented Jul 18, 2011 at 13:26
• @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. Commented Jul 18, 2011 at 13:56
• Anyway, your answer is interesting for me and deserves upvote. Commented Jul 18, 2011 at 14:02
• (Edit: Nevermind. :)) Commented Jul 19, 2011 at 15:04

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.

• I've edited my question to "Does anyone know some candidate problems ... ?" Commented Jul 15, 2011 at 9:42