¿Hay problemas conocidos de NP completo, ni NP-hard en el sentido fuerte ni tener un algoritmo pseudopolinomial?

En su artículo (p. 503), Garey y Johnson comentan:

... podría existir un problema de NP-completo que no es NP-completo en sentido estricto ni resuelto por un algoritmo de tiempo pseudo-polinomial ...

¿Alguien sabe algunos problemas candidatos con las propiedades mencionadas anteriormente?

Creo que la posible respuesta a esta pregunta puede ser una lista de problemas NP-completos en el sentido ordinario, de modo que no se conozca ningún algoritmo pseudopolinomial para ellos.

No sé si está interesado en escuchar más detalles de mi comentario sobre su pregunta, pero aquí hay más detalles de todos modos.

Si P = NP, cada problema en NP se puede resolver en tiempo polinómico y, por lo tanto, en tiempo pseudopolinómico, lo que significa que ningún problema satisface su requerimiento, como Magnus señaló en su respuesta. Supongamos que P ≠ NP en el resto de esta respuesta.

Debido a que P ≠ NP, existe un lenguaje L ∈NP ∖ P que no es NP completo (teorema de Ladner). Considere el siguiente problema:

Producto directo de Partición e
Instancia L : m enteros positivos a ₁ , ..., a _m y k enteros b ₁ , ..., b _k ∈ {0,1}.
Pregunta : ¿Se cumplen los dos siguientes?
(1) Los m enteros a ₁ , ..., a _m forman una instancia de sí del problema de Partición.
(2) El k cadena de bits b ₁ ... b _k pertenece a L .

Siguiendo el artículo de Garey y Johnson, defina la función Longitud como m + ⌈log max _i a _i ⌉ + k y la función Max como max _i a _i .

Es una rutina verificar (i) que es NP-completo en el sentido débil, (ii) que no tiene un algoritmo de tiempo pseudo-polinomial, y (iii) que no es NP-completo en el fuerte sentido.

(Sugerencias: (i) La pertenencia a NP se debe al hecho de que tanto el problema de Partición como L están en NP. Para la dureza de NP, reduzca la Partición a este problema. (Ii) Construya una transformación pseudo-polinomial de L a este problema. (iii) Construya una transformación pseudo-polinomial de este problema a L usando el hecho de que Partition tiene un algoritmo de tiempo pseudo-polinomial).

No hay nada especial sobre el problema de Partición en esta construcción: puede usar su problema favorito de NP débilmente completo con un algoritmo de tiempo pseudopolinomial.

Diría que la respuesta es claramente no (es decir, nadie lo sabe), porque nadie sabe si los problemas de NP completo se pueden resolver en tiempo polinomial , y mucho menos en tiempo pseudo- polinomial. (Cada algoritmo polinomial es, por supuesto, pseudopolinomial). Si puede encontrar un problema en NPC que no se puede resolver en tiempo pseudopolinomial, acaba de demostrar que P ≠ NP, por lo que creo que es seguro decir que no habrá tales ejemplos producido en cualquier momento pronto.