19

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.

Oleksandr Bondarenko
  • 4,215
  • 1
  • 25
  • 46
  • 5
    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 Jul 14 '11 at 18:49
  • 2
    My answer posted earlier was incorrect; my apologies. This is what happens when I hand-wave and post! – Daniel Apon Jul 18 '11 at 04:12

2 Answers2

17

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 b1…bk 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.

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • 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 Jul 18 '11 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. – Tsuyoshi Ito Jul 18 '11 at 13:56
  • Anyway, your answer is interesting for me and deserves upvote. – Oleksandr Bondarenko Jul 18 '11 at 14:02
  • (Edit: Nevermind. :)) – Daniel Apon Jul 19 '11 at 15:04
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.

Magnus Lie Hetland
  • 1,520
  • 10
  • 17