Problemas intermediários -complete?

O problema de partição é fracamente NP-completo, pois possui algoritmo de tempo polinomial (pseudo-polinomial) se os números inteiros de entrada estiverem delimitados por algum polinômio. No entanto, 3-Partition é um problema fortemente completo de NP, mesmo que números inteiros de entrada sejam limitados por um polinômio.

Supondo, , podemos provar que problemas intermediários completos de NP devem existir? Se a resposta for sim, existe um problema candidato "natural"?$\mathsf{P \ne NP}$

Aqui, o problema intermediário NP-completo é um problema que não possui um algoritmo de tempo pseudo-polinomial nem NP-completo no sentido forte.

Eu acho que existe uma hierarquia infinita de problemas intermediários completos de NP entre a completude fraca e a completude forte.

Edição 6 de março : Como mencionado nos comentários, uma maneira alternativa de fazer a pergunta é:

Supondo, , podemos provar a existência de problemas de NP-completo que não possuem algoritmo de tempo polinomial nem NP-completo quando as entradas numéricas são apresentadas como unárias? Se a resposta for sim, existe um problema candidato "natural"?$\mathsf{P \ne NP}$

EDIT2 6 de março : A direção inversa da implicação é verdadeira. A existência de tais "intermediários" problemas -Complete implica uma vez que se então unárias problemas -Complete estão em .P ≠ N P P = N P N P $NP$$\mathsf{P \ne NP}$$\mathsf{ P=NP}$$NP$$P$

Esta é uma resposta parcial que fornece apenas a um candidato um intermediário de intermediário .$NP$

n A = { um 1 , . . . , Um n } k S 1 , . . . , S k ⊆ { um 1 , . . . , a n } s u m ( S 1 ) = . . . = s u m ( S k$k$ Problema nos subconjuntos de soma igual: dado um multiset de inteiros positivos , existem subconjuntos não vazios tal que ?$n$$A = \{a_1,...,a_n\}$$k$$S_1,...,S_k ⊆ \{a_1,...,a_n\}$$sum(S_1) = ... = sum(S_k)$

O problema é fracamente completo em quando e, portanto, possui um algoritmo de tempo pseudo-polinomial para qualquer número inteiro constante fixo . No entanto, torna-se fortemente completo quando o número de subconjuntos de soma igual .k = O ( 1 ) k > 2 N P k = Ω ( n $NP$$k= O(1)$$k > 2$$NP$$k= \Omega(n)$

Se e , o problema -Equal Sum Subsets é um problema candidato intermediário- intermediário (conforme descrito na pergunta). Esse problema não é conhecido por ter um algoritmo de tempo pseudo-polinomial, nem provado ser completo no sentido forte.k = O ( log n ) k N P N $k= \omega(1)$$k= O(\log n)$$k$$NP$$NP$

Referência:

CIELIEBAK, EIDENBENZ, PAGOURTZIS e SCHLUDE, SOBRE A COMPLEXIDADE DAS VARIAÇÕES DE IGUALDADE DE SUBJETIVOS IGUAIS, Nordic Journal of Computing 14 (2008), 151–172