¿Problemas intermedios -completos?

El problema de partición es débilmente NP-completo ya que tiene un algoritmo de tiempo polinomial (pseudo-polinomial) si los enteros de entrada están limitados por algún polinomio. Sin embargo, 3-Partition es un problema NP-completo, incluso si los enteros de entrada están delimitados por un polinomio.

Suponiendo, , ¿podemos demostrar que deben existir problemas intermedios de NP completo? Si la respuesta es sí, ¿existe tal problema candidato "natural"?$\mathsf{P \ne NP}$

Aquí, el problema NP-complete intermedio es un problema que ni tiene un algoritmo de tiempo pseudo-polinomial ni NP-complete en sentido estricto.

Supongo que existe una jerarquía infinita de problemas intermedios de NP completo entre la integridad de NP débil y la integridad de NP fuerte.

EDITAR 6 de marzo : como se menciona en los comentarios, una forma alternativa de plantear la pregunta es:

Suponiendo que , ¿podemos demostrar la existencia de problemas de NP completo que no tienen algoritmo de tiempo polinómico ni NP completo cuando las entradas numéricas se presentan en unario? Si la respuesta es sí, ¿existe tal problema candidato "natural"?$\mathsf{P \ne NP}$

EDIT2 6 de marzo : La dirección inversa de la implicación es verdadera. La existencia de tales "intermedias" problemas -Complete implica ya que si entonces unarios problemas -Complete están en .$NP$$\mathsf{P \ne NP}$$\mathsf{ P=NP}$$NP$$P$

Esta es una respuesta parcial que solo le da a un candidato un intermedio de completo.$NP$

n A = { a 1 , . . . , Un n } k S 1 , . . . , S k ⊆ { a 1 , . . . , a n } s u m ( S 1 ) = . . . = s u m ( S k$k$ Problema de subconjuntos de suma igual: dado un conjunto múltiple de enteros positivos , ¿hay subconjuntos no vacíos disjuntos tal que ?$n$$A = \{a_1,...,a_n\}$$k$$S_1,...,S_k ⊆ \{a_1,...,a_n\}$$sum(S_1) = ... = sum(S_k)$

El problema es débilmente completo cuando y, por lo tanto, tiene un algoritmo de tiempo pseudo-polinomial para cualquier entero constante fijo . Sin embargo, se vuelve fuertemente completo cuando el número de subconjuntos de suma igual .$NP$$k= O(1)$$k > 2$$NP$$k= \Omega(n)$

Si y entonces -Igual problema de la suma de subconjuntos es un candidato intermedio problema -Complete (como se describe en la pregunta). No se sabe que este problema tenga un algoritmo de tiempo pseudo-polinomial ni se ha demostrado que sea completo en el sentido más estricto.$k= \omega(1)$$k= O(\log n)$$k$$NP$$NP$

Referencia:

CIELIEBAK, EIDENBENZ, PAGOURTZIS y SCHLUDE, SOBRE LA COMPLEJIDAD DE LAS VARIACIONES DE LOS EQUIPOS DE SUMAS IGUALES, Nordic Journal of Computing 14 (2008), 151–172