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.
Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?
ds.algorithms;np hardness;np
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 PNP in the rest of this answer.Because PNP, there exists a language LNPP which is not NP-complete (Ladners theorem).  Consider the following problem:Direct product of Partition and LInstance: 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.