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.

Improve this question
$\endgroup$
2
  • 5
    $\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
    Commented Jul 14, 2011 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
    Commented Jul 18, 2011 at 4:12

2 Answers 2

Reset to default
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 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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Jul 18, 2011 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
    Commented Jul 18, 2011 at 13:56
  • $\begingroup$ Anyway, your answer is interesting for me and deserves upvote. $\endgroup$
    – Oleksandr Bondarenko
    Commented Jul 18, 2011 at 14:02
  • $\begingroup$ (Edit: Nevermind. :)) $\endgroup$
    – Daniel Apon
    Commented Jul 19, 2011 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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