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 ponieważ jeżeli następnie unarne pełnoporcjowych problemy w . $NP$ $\mathsf{P \ne NP}$ $\mathsf{ P=NP}$ $NP$ $P$

cc.complexity-theory np-hardness partition-problem

— Mohammad Al-Turkistany
źródło

@MarzioDeBiasi Istnieje inna definicja silnej kompletności NP (może być mniej popularna), która definiuje problem numeryczny jako NP-zupełny, nawet jeśli wszystkie liczby całkowite wejściowe są reprezentowane w notacji jednoargumentowej.

— Mohammad Al-Turkistany

@vzn jest to absurdalny komentarz! 1) thm ladnera nie dotyczy np. Trudnych problemów, które nie są na przykład kompletne; 2) podczas gdy Mohammad jest rodzajem przeciążającej terminologii, jasno określa swoją klasę problemów (NPC, niezbyt silnie NPC i brak algorytmu czasowego pseudopolu) i różni się od NPC.

— Sasho Nikolov

@ MohammadAl-Turkistany: ok, dziękuję, być może sugeruję, byś nazwał to jednoznaczną NP-kompletnością, jak u Garey i Johnsona „Strong” NP-Completeness Wyniki: Motywacja, przykłady i implikacje . Szukacie więc problemów pośrednich między jednoargumentowym NPC a pseudopolimialnym NPC. Wciąż próbuję to jednak zrozumieć, w swojej pracy G&J mówi (o jednoosobowym NPC): „... Nietrudno dostrzec, że odpowiada to naszemu przekonaniu o silnej kompletności NP…”.

— Marzio De Biasi

@MarzioDeBiasi Myślę, że chodzi o to, że możemy (->) podać binarną liczbę wielomianu wielkości na wejściu, przekonwertować ją na unarny w czasie polytime i uruchomić algorytm jednoargumentowy, (<-) podając jednoargumentowe wejście długości poli w reszta danych wejściowych, przeczytaj całość i przekonwertuj ją na binarną i uruchom algorytm binarny.

— usul

Ponieważ każdy problem, który ma algorytm wielomianowy, jeśli jeden z parametrów wejściowych jest ustalony, występuje w FPT, wydaje się, że zasadniczo pytasz, czy występują problemy trudniejsze niż FPT, ale nie W [1]. O ile mi wiadomo, twierdzenie Ladnera można rozszerzyć na to ustawienie; może być w podręczniku Flum / Grohe.

— András Salamon,

$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

— Mohammad Al-Turkistany
źródło

Czy widziałeś to cstheory.stackexchange.com/a/7427/15637 ?

— Thomas Kalinowski

Tak. Ta odpowiedź stanowi prawdopodobnie sztuczny problem.

— Mohammad Al-Turkistany