Sunday, July 17, 2011

NP-complete problem which is neither NP-complete in the strong sense nor solvable by pseudopolynomial algorithms?

Recently I've posted on cstheory a question that is described in the title of this post. Since then I've received only one comment and one answer. I think the possible answer to it can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.