Problemy między P a NPC

Rozkładanie na czynniki i izomorfizm wykresów są problemami w NP, o których nie wiadomo, że są w P ani w NP-kompletne. Jakie są inne (wystarczająco różne) naturalne problemy, które dzielą tę właściwość? Sztuczne przykłady pochodzące bezpośrednio z dowodu twierdzenia Ladnera się nie liczą.

Czy którykolwiek z tych przykładów może być pośrednio NP, zakładając jedynie „rozsądną” hipotezę?

Oto zbiór niektórych odpowiedzi na problemy między P i NPC:

• Faktoring
• Problemy z izomorfizmem: Wykres Izomorfizm [nie NPC, chyba że ] (przez @Jeff Kinne), Graf Automorfizm, Grupowy Izomorfizm, Automorfizm, Izomorfizm Pierścieniowy i Automorfizm (przez @Joshua Grochow)$\sum_2^p=\prod_2^p$
• Obliczanie odległości obrotu między dwoma drzewami binarnymi lub odległości przerzucenia między dwoma triangulacjami tego samego zestawu punktów płaskich (przez @David Eppstein)
• Problem rogatki w rekonstrukcji punktów na linii z odległości (via @Suresh Venkat)
• Problemy wynikające z hipotez unikalnych gier (via @Moritz)
• Dyskretny problem z logami i inne związane z założeniami kryptograficznymi (via @Joe Fitzsimons)
• Określenie zwycięzcy w grach parzystości (via @mashca)
• Ustalenie, kto ma największą szansę na wygraną w grze stochastycznej (przez @Peter Shor na MO)
• Problemy z numerami w skrzynkach (przez @Joshua Grochow)
• Kontrola agendy dla zrównoważonych turniejów z pojedynczą eliminacją (via @virgi)
• Trywialność węzłów (przez @JeffE)
• (Przy założeniu NEXP ≠ exp) wyłożone wersje NEXP problemów -Complete (przez @Joshua Grochowie)
• Problemy z TFNP (przez @Marcos Villagra)
• Przecięcie monotonu SAT (via @ András Salamon)
• Problem minimalnego rozmiaru obwodu (przez @Eric Allender)
• Zdecydowanie, czy dany triangulowany 3-kolektor jest 3-kulą (przez @Joe O'Rourke i @Peter Shor)
• Cięcia Problem Zdjęcie ze stałą liczbą długości obiektu (poprzez @Suresh venkat)
• Monotone Self-Duality (via @Danu)
• Płaska minimalna bisekcja (via @turkistany)
• Pigeonhole Subset Sum (via @ user834)
• Sumy pierwiastka kwadratowego (via @JeffE)
• Decyzja, czy wykres dopuszcza pełne wdzięku etykietowanie (przez @Oleksandr Bondarenko)
• Wersja szczelinowa najbliższego wektora w problemie sieci GapCVP (przez @MCH)$(\sqrt{n})$
• Liniowy podzielność problemu [wiadomo, że -Complete ale NPC] (przez @Oleksandr Bondarenko)$\gamma$
• Znalezienie wymiaru VC (przez @Mohammad al Turkistany)
• Znalezienie minimalnego dominującego zestawu w turnieju (przez @Mohammad al Turkistany)
• Grupowana planarność

Mój ulubiony problem w tej klasie (sformułuję to jako problem funkcjonalny, ale łatwo przekształcić go w problem decyzyjny w standardowy sposób): obliczyć odległość obrotu między dwoma drzewami binarnymi (równoważnie odległość odwrócenia między dwoma triangulacjami wypukły wielokąt).

Problem, który nie jest wymieniony ani na tej liście, ani na liście MO, to problem rogatek. Biorąc pod uwagę wielokrotność n (n-1) / 2 liczb, każda liczba reprezentująca odległość między dwoma punktami na linii, rekonstruuje pozycje pierwotnych punktów.

Zauważ, że to, co czyni tę nietrywialną, to fakt, że dla danej liczby d w multisecie nie wiesz, która para punktów dzieli d jednostek.

Chociaż wiadomo, że w danym przypadku istnieje tylko wielomianowa liczba rozwiązań, nie wiadomo, jak je znaleźć!

Problem sumy pierwiastków kwadratowych: Biorąc pod uwagę dwie sekwencje i b 1 , b 2 , … , b n liczb całkowitych dodatnich, wynosi A : = ∑ i $a_1, a_2, \dots, a_n$$b_1, b_2, \dots, b_n$ mniejsze niż, równe lub większe niżB:=∑i$A := \sum_i \sqrt{a_i}$ ?$B := \sum_i \sqrt{b_i}$

• Problem ma trywialny algorytm czasu na prawdziwej pamięci RAM - wystarczy obliczyć sumy i porównać je! - ale to nie oznacza członkostwa w P.$O(n)$

• Istnieje oczywisty algorytm o skończonej precyzji, ale nie wiadomo, czy wielomianowa liczba bitów precyzji jest wystarczająca do poprawności. (Szczegółowe informacje można znaleźć na stronie http://maven.smith.edu/~orourke/TOPP/P33.html .)

• Twierdzenie Pitogorasa oznacza, że ​​długość dowolnej krzywej wielobocznej, której wierzchołki i punkty końcowe liczb całkowitych jest sumą pierwiastków kwadratowych liczb całkowitych. Zatem problem sumy korzeni jest nieodłącznie związany z kilkoma płaskimi problemami z geometrią obliczeniową, w tym z euklidesowymi minimalnymi drzewami spinającymi , najkrótszymi ścieżkami euklidesowymi , triangulacjami o minimalnej wadze i problemem euklidesowego sprzedawcy podróżującego . (Problem euklidesowy MST można rozwiązać w czasie wielomianowym bez rozwiązania problemu sumy korzeni, dzięki podstawowej strukturze matroidu i faktowi, że EMST jest subgrafem triangulacji Delaunaya.)

• Nie jest wielomianem czasie randomizowane algorytm, z powodu Johannes Blömer , aby zdecydować, czy te dwie kwoty są równe. Jeśli jednak odpowiedź brzmi „nie”, algorytm Blömera nie określa, która suma jest większa.

• Wersja decyzyjna tego problemu (Czy ?) Nie jest nawet znana z NP. Jednak algorytm Blömera implikuje, że jeśli problem decyzyjny dotyczy NP, to dotyczy to również NP. Zatem jest mało prawdopodobne, aby problem został zakończony NP.$A > B$

Oto lista problemów, które mogą kwalifikować się jako „wystarczająco” różne. Na podstawie tego samego dowodu, co w przypadku izomorfizmu grafowego, jeśli którykolwiek z nich jest NP-kompletny, to hierarchia wielomianowa zapada się na drugi poziom. Nie sądzę, aby istniał jakikolwiek szeroki konsensus co do tego, który z tych „powinien” być w P.

• Automorfizm wykresów (określ, czy wykres ma nietrywialny automorfizm). Redukuje do izomorfizmu grafowego, ale nie wiadomo (nie sądzono?), Że jest trudne do oznaczenia.
• Grupowy izomorfizm i automorfizm (gdzie grupy są podane przez ich tabliczki mnożenia). Znów, redukuje się do izomorfizmu grafów, ale nie uważa się, że jest trudny do oznaczenia.
• Izomorfizm pierścieniowy i automorfizm. W pewnym sensie jest to dziadek wszystkich powyższych problemów, ponieważ faktoring całkowity jest równoznaczny ze znalezieniem nietrywialnego automorfizmu pierścienia, a wykres Izomorfizm sprowadza się do Izomorfizmu Pierścienia. Zobacz Neeraj Kayal, Nitin Saxena. Złożoność problemów morfizmu pierścieniowego. Złożoność obliczeniowa 15 (4): 342–390 (2006). (Co ciekawe, określenie, czy pierścień ma nietrywialny automorfizm, znajduje się w )$P$
• Ten post Billa Gasarcha zawiera kilka innych problemów ze smakiem teorii Ramseya, które wyglądają, jakby były pośrednie.
• Zgodnie z twierdzeniem Mahaneya żaden zestaw rzadki nie może być NP-kompletny. Ale wiemy też, że istnieją nieliczne zestawy w - P wtw N E X P nie jest równe E X P . Zakładając, że N E X P ≠ E X P , wyściełana wersja dowolnego problemu N E X P ma pośrednią złożoność. (Taki aparat nie może być w P chyba N E X P = E X $NP$$P$$NEXP$$EXP$$NEXP \neq EXP$$NEXP$$P$$NEXP = EXP$, co jest sprzeczne z naszym założeniem.) Istnieje wiele naturalnych problemów z kompletnością $NEXP$

Problem minimalnego rozmiaru obwodu (MCSP) jest moim ulubionym „naturalnym” problemem w NP, który nie jest znany jako NP-zupełny: biorąc pod uwagę tabelę prawdy (o wielkości n = 2 ^ m) m-zmiennej funkcji boolowskiej f, i biorąc pod uwagę liczbę s, czy f ma obwód o rozmiarze s? Jeśli MCSP jest łatwe, to nie ma zabezpieczonej kryptograficznie jednokierunkowej funkcji. Ten problem i jego warianty stanowiły dużą motywację do badania algorytmów „brutalnej siły” w Rosji, co doprowadziło do prac Levina nad kompletnością NP. Problem ten można również rozpatrywać w kategoriach złożoności Kołmogorowa związanej z zasobami: pytanie, czy można szybko odzyskać ciąg z krótkiego opisu. Ta wersja problemu została zbadana przez Ko; nazwa MCSP została użyta po raz pierwszy przez Cai i Kabanets, o ile mi wiadomo. Więcej referencji można znaleźć w niektórych moich artykułach: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf

Monotonia samo-dualność

Dla dowolnej funkcji boolowskiej $f=f(x_1, x_2, ..., x_n)$ , to jest podwójna$f^d=\bar{f}(\bar{x_1}, \bar{x_2}, ..., \bar{x_n})$ . Biorąc pod uwagę,$f(x_1, x_2, ..., x_n)$reprezentowane przez formułę CNF, musimy zdecydować, czy $f=f^d$ .

Problem ten występuje w ko-NP [ $\log^2 n$ ], tzn. Można go rozstrzygać o krokach niedeterministycznych $O(\log^2n/ \log\log n)$ . Zatem ma on quasi-wielomianowy algorytm czasu (czas $O(n^{\log n/\log \log n})$ ), a zatem jest mało prawdopodobne, aby był współ-NP-twardy.

Nadal jest otwarte, czy ten problem występuje w P, czy nie. Więcej szczegółów można znaleźć w artykule z 2008 r. „ Obliczeniowe aspekty dualizacji monotonicznej: krótka ankieta ” autorstwa Thomasa Eitera, Kazuhisy Makino i Georga Gottloba.

Trywialność węzłów: biorąc pod uwagę zamknięty łańcuch wielokątny w 3-przestrzeni, czy nie jest on wiązany (tj. Otoczenia izotopowy do płaskiego koła)?

Wiadomo, że jest to w NP dzięki głębokim wynikom w teorii normalnej powierzchni, ale nie jest znany żaden algorytm wieloczasowy ani dowód twardości NP.

Nie wiadomo, czy w czasie wielomianowym można zdecydować, czy gracz 1 ma strategię wygrywającą w grze parzystej (z danej pozycji początkowej). Problem jest jednak zawarty w NP i co-NP, a nawet w UP i co-UP.

Otrzymujesz bardzo długą listę problemów, jeśli chcesz zaakceptować problemy z aproksymacją, takie jak przybliżenie Max-Cut do współczynnika 0,878. Nie wiemy, czy jest to NP-trudny czy w P (znamy tylko twardość NP, zakładając hipotezę gry Uniuqe).

W monotonnej formule CNF każda klauzula zawiera tylko literały dodatnie lub tylko literały ujemne. W przecinającej się monotonicznej formule CNF każda dodatnia klauzula ma pewną zmienną wspólną z każdą klauzulą ​​ujemną.

Problem decyzyjny

INTERSECTING MONOTONE SAT
Wejście: przecinający monotoniczny wzór CNF Pytanie: czy f jest zadowalające?$f$
$f$

ma algorytm sięga roku 1996, lecz nie jest znany w P. (Oczywiście, może okazać się w p, ale byłoby to istotny postęp).$n^{o(\log\ n)}$

• Thomas Eiter i Georg Gottlob, Hypergraph Transversal Computation and Related Problems in Logic and AI , JELIA 2002. doi: 10.1007 / 3-540-45757-7_53

Czy dany triangulowany 3-kolektor jest 3-kulą? Od Joe O'Rourke.

Wersja Pigeonhole Subset Sum (lub Subset Sum Equality).

Dany:

Zgodnie z zasadą szufladki muszą istnieć dwa rozłączne podzbiory, takie, że:$S_1, S_2 \subseteq \{ 1, \dots, n \}$

Problem sumy podzbiorów szuflad prosi o takie rozwiązanie. Pierwotnie stwierdzono w „ Efektywnych algorytmach aproksymacyjnych dla problemu RÓWNOŚCI PODSET-SUMS ” autorstwa Bazgana, Santha i Tuza.

Istnieje wiele problemów związanych ze znajdowaniem ukrytych podgrup. Wspomniałeś o faktoringu, ale jest też problem z dyskretnym logiem, a także inne związane z krzywymi eliptycznymi itp.

Oto problem związany z komputerowym wyborem społecznym, o którym nie wiadomo, że jest w P, i może, ale nie musi być NP-zupełny.

Kontrola agendy dla zrównoważonych turniejów z pojedynczą eliminacją:

Biorąc pod uwagę: wykres turniejowy na n $T$ węzłów, węzeł$n=2^k$$a$

Pytanie: czy istnieje permutacja węzłów ( nawias ), aby a był zwycięzcą zaindukowanego turnieju pojedynczej eliminacji?

Biorąc pod uwagę permutację na 2 K węzłów V i turnieju wykres T o V można otrzymać permutacji P k - 1 na 2 k - 1 węzły, jak następuje. Dla każdego i > 0 rozważmy P k [ 2 i - 1 ] i P k [ 2 i ] oraz łuk e między nimi w$P_k$$2^k$$V$$T$$V$$P_{k-1}$$2^{k-1}$$i>0$$P_k[2i-1]$$P_k[2i]$$e$ ; niech P $T$jeślie=( P k [2i-1], P k [2i])i P k - 1 [i]= P k [2i] wprzeciwnym razie . Oznacza to, że dopasowujemy pary węzłów zgodnie z P k i używamy$P_{k-1}[i]=P_k[2i-1]$$e=(P_k[2i-1],P_k[2i])$$P_{k-1}[i]=P_k[2i]$$P_k$$T$ decyzją, które węzły (zwycięzcy) przechodzą do następnej rundy $P_{k-1}$. Stąd, biorąc pod uwagę permutację na można faktycznie zdefiniować k rund P k - 1 , … , P $2^k$$k$$P_{k-1},\ldots,P_0$ indukcyjnie jak wyżej, aż do ostatniego permutacji zawiera tylko jeden węzeł. Definiuje to (zrównoważony) turniej pojedynczej eliminacji na . Węzłów. Węzeł, który pozostaje po wszystkich rundach, jest zwycięzcą turnieju.$2^k$

Kontrola agendy dla zrównoważonych turniejów z pojedynczą eliminacją (formułowanie wykresu):

Biorąc pod uwagę: wykres turniejowy na n = 2 $T$$n=2^k$ węzłów, węzeł$a$

Pytanie: czy zawiera (rozciągający się) dwumianowy arborescencję na 2 $T$$2^k$ węzłów zakorzenione w ?$a$

Dwumianowego arborescence na węzłów sadzonek przez węzeł X jest zdefiniowany rekurencyjnie za pomocą dwumianowego arborescence na 2 k - 1 węzłów zakorzenione w X i dwumianowego arborescence na 2 k - 1 węzłów zakorzenione w węźle innym Y i kątowych od x do y . (Jeśli k = 0 , dwumianowa arborescencja jest tylko pierwiastkiem.) Obejmujące dwumianowe arborescencje na wykresie turnieju przechwytują dokładnie turnieje z pojedynczą eliminacją, w których można grać, biorąc pod uwagę informacje o wyniku meczu na wykresie turnieju.$2^k$$x$$a$$2^{k-1}$$x$$2^{k-1}$$y$$x$$y$$k=0$

Niektóre referencje:

1. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: Zwycięzca Determinacja w głosowaniu sekwencyjnym większością głosów. IJCAI 2007: 1372–1377.
2. N. Hazon, PE Dunne, S. Kraus i M. Wooldridge. Jak organizować wybory i konkursy. COMSOC 2008.
3. Thuc Vu, Alon Altman, Yoav Shoham. O złożoności problemów związanych z kontrolą harmonogramu w turniejach nokautowych. AAMAS (1) 2009: 225–232.
4. V. Vassilevska Williams. Naprawianie turnieju. AAAI 2010.

Spójrz na klasę TFNP . Ma wiele problemów z wyszukiwaniem o statusie pośrednim.

Problem wywołanego izomorfizmu subgrafu ma niekompletne NP „ograniczenia po lewej stronie”, zakładając, że P nie jest równe NP. Patrz Y. Chen, M. Thurley, M. Weyer: Zrozumienie złożoności indukowanych izomorfizmów subgrafu, ICALP 2008.

Złożoność problemu płaskie minimum równego podziału jest intrygującym otwarty problem, który nie jest znany -hard. W przeciwieństwie do tego, planarny problem maksymalnego bisekcji to N P- twardy.$NP$$NP$

Problem minimalnej bisekcji: Znajdź podział zestawu węzłów na dwie równe części, tak aby zminimalizować liczbę przecinających się krawędzi.

Karpiński, Przybliżenie problemu minimalnej bisekcji: wyzwanie algorytmiczne

Problem z materiałem tnącym przy stałej liczbie długości obiektów. Zobacz tę dyskusję, aby uzyskać więcej informacji.

Wersja szczelinowa najbliższego wektora w problemie z siecią jest następująca: Biorąc pod uwagę podstawę dla wymiarowej sieci i wektora v , należy rozróżnić dwa przypadki, w których wektor sieci znajduje się w odległości co najwyżej 1 od v lub gdy każdy wektor sieci jest β- daleki od v , dla niektórych parametrów stałej szczeliny β > $n$$v$$1$$v$$\beta$$v$$\beta > 1$ .

, problem jestNP∩CONPa więc mało prawdopodobne,NP-Complete (i przypuszcza się pozaP). Ten przypadek znajduje się w centrum zainteresowania kryptografii opartej na sieci i związanego z nią problemu ukrytych podgrup dwuściennych w obliczeniach kwantowych. Powiedzmy, żegdyβjest znacznie mniejsze$\beta = \sqrt{n}$$\mathsf{NP} \cap \mathsf{coNP}$$\mathsf{NP}$$\mathsf{P}$$\beta$$\beta = n^{o(1/\log \log n)}$$\mathsf{NP}$

$G = (V,E)$$f$$v\in V$$f(v)$$e = uv\in E$$|f(u) − f(v)|$$f : V\rightarrow \{0, 1, 2,\dots, |E|\}$$\{1, 2,..., |E|\}$

1. JA Gallian. Dynamiczne badanie etykietowania wykresów. The Electronic Journal of Combinatorics, 2009.
2. DS Johnson. Kolumna NP-kompletność: Ciągły przewodnik. J. Al Algorytmy, 4 (1): 87–100, 1983.
3. DS Johnson. Kolumna NP-kompletność. Transakcje ACM na algorytmach, 1 (1): 160–176, 2005.

$P$$NP$$O(n^{\log n})$$NP$$NP$

$a$$b$$a \cdot x+1$$b$

$\gamma$

Garey i Johnson w swoim przełomowym „Komputery i nienaruszalność” mówią, że (s. 158–159):

$\gamma$$R_M$$M$

$$R_M=\{\langle x,y\rangle:there\ is\ a\ string\ z\ such\ that\ on\ input\ x\ and\ guess\ z\ M\ has\ output\ y\}$$

$L_1$$\Sigma_1$$\gamma$$L_2$$\Sigma_2$$L_1\propto_{\gamma}L_2$$M$$x\in\Sigma_1^*$$y\in\Sigma_2^*$$\langle x,y\rangle\in R_M$$\langle x,y\rangle\in R_M$$x\in L_1$$y\in L_2$$M$$x$$x$$x$$L_2$$x\in L_1$

$P$$NP$$O(n^{\log n})$

Uważa się, że następujący problem jest NP-średniozaawansowany, tj. Nie dotyczy NP, ale ani P, ani NP-zupełny.

Wykładniczy wielomianowy problem z korzeniem (EPRP)

$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

$\deg(p)=0$

Aby uzyskać dodatkowe informacje, patrz moje pytanie i powiązaną dyskusję .

Nie wiem, czy problem ważonego izomorfizmu hipergrograficznego zaproponowany w odpowiedzi przez Thinha D. Nguyena nie może być po prostu wykazany jako kompletny. Istnieje jednak problem związany z GI ściśle związany z GI, który nie został jeszcze zredukowany do GI, a mianowicie problem izomorfizmu strunowego (zwany również problemem izomorfizmu barwnego ). Jest to problem, który László Babai rzeczywiście przedstawił w quasi-wielomianowym czasie. Jest niezależny, ponieważ jest równoważny z wieloma problemami decyzyjnymi w teorii grup (permutacji):

• problem przecięcia coseta
• problem z testowaniem członkostwa w Double Coset
• problem faktoryzacji grupowej

Problemem, o którym nie wiadomo, że jest ani w FP, ani w NP-twardym, jest problem znalezienia minimalnego drzewa Steiner, gdy obiecuje się, że wierzchołki Steiner spadną na dwa odcinki linii prostej przecinające się pod kątem 120 °. Jeśli kąt między segmentami linii jest mniejszy niż 120 °, to problem jest trudny dla NP. Przypuszcza się, że gdy kąt jest większy niż 120 °, problem występuje w FP.

Dlatego wydaje się, że następujący problem decyzyjny ma obecnie pośrednią złożoność:

$q$
$q$

Oczywiście może to być w P lub NP-zupełne, ale wydaje się, że mielibyśmy interesującą dychotomię przy 120 ° zamiast problemu pośredniego. (Przypuszczenie może być również fałszywe).

• JH Rubinstein, DA Thomas, NC Wormald, Steiner Trees for Terminals Ograniczone do krzywych , SIAM J. Discrete Math. 10 (1) 1–17, 1997. doi: 10.1137 / S0895480192241190

Problemem trudnym dla GI, o którym nie wiadomo, że jest NP-complete, może być WAGA_HYPERGRAPH_ISOMORPHISM. Dostajesz dwa hipergrrafy$G_1$ i $G_2$ na $n$ wierzchołki z ważonymi hiper-krawędziami decydują, czy istnieje permutacja wierzchołków $\pi$ obrócenie $G_1$ w $G_2$. Zobacz także: Problem z trudnym grafem GI nie jest znany$NP$-kompletny