19
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Jul 14 '11 at 18:49
  • 2
    $\begingroup$ My answer posted earlier was incorrect; my apologies. This is what happens when I hand-wave and post! $\endgroup$ – Daniel Apon Jul 18 '11 at 4:12
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Oleksandr Bondarenko Jul 18 '11 at 13:26
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Jul 18 '11 at 13:56
  • $\begingroup$ Anyway, your answer is interesting for me and deserves upvote. $\endgroup$ – Oleksandr Bondarenko Jul 18 '11 at 14:02
  • $\begingroup$ (Edit: Nevermind. :)) $\endgroup$ – Daniel Apon Jul 19 '11 at 15:04
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I've edited my question to "Does anyone know some candidate problems ... ?" $\endgroup$ – Oleksandr Bondarenko Jul 15 '11 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.