Produkt pośredni

Problem podziału jest słabo NP-zupełny, ponieważ ma wielomianowy (pseudo-wielomianowy) algorytm czasowy, jeśli wejściowe liczby całkowite są ograniczone przez jakiś wielomian. Jednak 3-partycja jest silnym problemem NP-zupełnym, nawet jeśli wejściowe liczby całkowite są ograniczone przez wielomian.

Zakładając, , Czy możemy udowodnić, że pośrednie problemy NP-zupełne muszą istnieć? Jeśli odpowiedź brzmi „tak”, czy istnieje taki „naturalny” problem z kandydatem?$\mathsf{P \ne NP}$

Tutaj problem Pośredniego kompletnego NP jest problemem, który nie ma ani algorytmu pseudo-wielomianowego czasu, ani NP-zupełnego sensu.

Wydaje mi się, że istnieje nieskończona hierarchia pośrednich problemów z całkowitą NP między słabą kompletnością NP a silną kompletnością NP.

EDYCJA 6 marca : Jak wspomniano w komentarzach, alternatywnym sposobem postawienia pytania jest:

Zakładając, , Czy możemy udowodnić istnienie problemów NP-zupełnych, które nie mają algorytmu wielomianowego czasu ani NP-zupełnego, gdy dane liczbowe są prezentowane w jedności? Jeśli odpowiedź brzmi „tak”, czy istnieje taki „naturalny” problem z kandydatem?$\mathsf{P \ne NP}$

EDIT2 6 marca : Odwrotny kierunek implikacji jest prawdziwy. Istnienie takich "pośrednie" -Complete problemów oznacza P ≠ N P ponieważ jeżeli P = N P następnie unarne N P pełnoporcjowych problemy w P .$NP$$\mathsf{P \ne NP}$$\mathsf{ P=NP}$$NP$$P$

$NP$

$k$$n$$A = \{a_1,...,a_n\}$$k$$S_1,...,S_k ⊆ \{a_1,...,a_n\}$$sum(S_1) = ... = sum(S_k)$

$NP$$k= O(1)$$k > 2$$NP$$k= \Omega(n)$

$k= \omega(1)$$k= O(\log n)$$k$$NP$$NP$

Odniesienie:

CIELIEBAK, EIDENBENZ, PAGOURTZIS i SCHLUDE, O ZŁOŻONOŚCI ODMIAN PODSETÓW RÓWNEJ SUMY, Nordic Journal of Computing 14 (2008), 151–172