Intermédiaire

Le problème de partition est faiblement NP-complet car il a un algorithme de temps polynomial (pseudo-polynomial) si les entiers d'entrée sont délimités par un polynôme. Cependant, la partition 3 est un problème fortement NP-complet même si les entiers d'entrée sont délimités par un polynôme.

En supposant, , pouvons-nous prouver que des problèmes NP-complets intermédiaires doivent exister? Si la réponse est oui, existe-t-il un tel problème candidat "naturel"?$\mathsf{P \ne NP}$

Ici, le problème intermédiaire NP-complet est un problème qui n'a ni algorithme temporel pseudo-polynomial ni NP-complet au sens fort.

Je suppose qu'il existe une hiérarchie infinie de problèmes intermédiaires NP-complets entre faible NP-complet et fort NP-complet.

EDIT 6 mars : Comme mentionné dans les commentaires, une autre façon de poser la question est:

En supposant, , pouvons-nous prouver l'existence de problèmes NP-complets qui n'ont ni algorithme de temps polynomial ni NP-complet lorsque les entrées numériques sont présentées en unaire? Si la réponse est oui, existe-t-il un tel problème candidat "naturel"?$\mathsf{P \ne NP}$

EDIT2 6 mars : Le sens inverse de l'implication est vrai. L'existence de ces « intermédiaires » problèmes COMPLETES implique P ≠ N P car si P = N P alors unaire N P problèmes COMPLETES sont en P .$NP$$\mathsf{P \ne NP}$$\mathsf{ P=NP}$$NP$$P$

Ceci est une réponse partielle qui donne seulement un candidat intermédiaire problème -complete.$NP$

-Egalité problème Somme Sousensembles: Étant donné un multiset de n entiers positifs A = { a 1 , . . . , Un n } , sont là k non videsousensembles disjoints S 1 , . . . , S k ⊆ { a 1 , . . . , a n } tel que s u m ( S 1 ) = . . $k$$n$$A = \{a_1,...,a_n\}$$k$$S_1,...,S_k ⊆ \{a_1,...,a_n\}$ ?$sum(S_1) = ... = sum(S_k)$

Le problème est faiblement -complet lorsque k = O ( 1 ) et a donc un algorithme de temps pseudo-polynomial pour tout entier constant fixe k > 2 . Cependant, il devient fortement N P -complet lorsque le nombre de sous-ensembles à somme égale k = Ω ( n ) .$NP$$k= O(1)$$k > 2$$NP$$k= \Omega(n)$

Si et k = O ( log n ) alors k -Egalité problème Somme des sous - ensembles est un candidat intermédiaire N P problème -complete (tel que décrit dans la question). Ce problème n'est ni connu pour avoir un algorithme de temps pseudo-polynomial ni avéré être N P- complet au sens fort.$k= \omega(1)$$k= O(\log n)$$k$$NP$$NP$

Référence:

CIELIEBAK, EIDENBENZ, PAGOURTZIS et SCHLUDE, SUR LA COMPLEXITÉ DES VARIATIONS DES SOUS-ENSEMBLES À SOMME ÉGALE, Nordic Journal of Computing 14 (2008), 151–172