Problemy między P a NPC

128

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ę?

Lev Reyzin
źródło
Istnieje podobne pytanie, które może się przydać: cstheory.stackexchange.com/questions/52/…
Daniel Apon
1
Podobne pytanie w MO, z kilkoma wskazówkami dotyczącymi problemów w NP i co-NP, ale nie wiadomo, że są w P: mathoverflow.net/questions/31821/…
András Salamon
1
Istnieje kilka klas złożoności między P i NP-complete, które są obecnie uważane za interesujące: PPAD, problemy, które są równoważne UGC, NP co-NP, BPP, ... Jeśli pytasz o dużą listę, może uczynisz to społecznością wiki, proszę?
András Salamon
Dziękuję Ci. Jestem świadomy twierdzenia Ladnera. Chyba prosiłem o „naturalne problemy”. Wydaje mi się, że PPAD ma równowagę Nasha, więc to się liczy ...
Lev Reyzin

Odpowiedzi:

105

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

Lev Reyzin
źródło
5
Tak, ta procedura działa jako „oficjalna” odpowiedź.
Suresh Venkat
12
Byłoby wspaniale móc dodać odpowiedź do listy obserwowanych osób. To na pewno byłoby moje.
András Salamon
9
Usuwam Planar MAX 2-SAT z listy, Guibas i in. w „Aproksymowanie wielokątów i podziałów przy użyciu minimalnych ścieżek linków” ( springerlink.com/content/y234m35416w043v1 )
Bob Fraser
7
Czy którykolwiek z tych przykładów jest w stanie udowodnić pośredni NP, zakładając tylko jakąś „rozsądną” hipotezę (tj. Hipotezę mniej trywialną niż „ten problem jest NP-pośredni”)? Jeśli tak, warto wspomnieć o tym na tej liście.
Timothy Chow,
3
@Timothy Chow: W przykładzie powyżej, zakładając, jest udokumentowany sposób pośredni, to zakładając, N E X P E X P , miękką wersję N E X P -Complete problemu jest provably ani N P -Complete przez Mahaney ani P , jak to jest sprzeczne N E X P E X P . NEXPEXPNEXPEXPNEXPNPPNEXPEXP
Joshua Grochow
45

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).

David Eppstein
źródło
1
To fajny problem: nie zdawałem sobie sprawy, że jest w stanie zawieszenia.
Suresh Venkat
3
Tak, też o tym nie wiedziałem! Biorąc pod uwagę wszystkie te problemy / odpowiedzi, zastanawiam się, czy są w stanie otchłani, ponieważ uważamy, że tak naprawdę są, czy też są bardziej jak PRIMES ...
Lev Reyzin
Ten problem i jego potencjalnie pośredni status powinny być bardziej znane. Czy możesz podać odniesienie? Ponadto, czy jest jakikolwiek wynik wskazujący, że nie jest on kompletny NP, tak jak w przypadku Izomorfizmu Grafów i powiązanych problemów?
Joshua Grochow
8
Bardzo ładnym i ważnym, ale starszym odniesieniem są Thurston, Sleator i Tarjan, „Odległość obrotu, triangulacje i geometria hiperboliczna”, STOC'86 i JAMS'88. Najnowsze odniesienie, które wyraźnie wspomina o złożoności problemu, ponieważ wciąż jest otwarte, patrz Lucas, „Zwiększony rozmiar jądra dla odległości obrotu w drzewach binarnych”, IPL 2010, dx.doi.org/10.1016/j.ipl.2010.04. 022
David Eppstein,
1
Ciekawy. Wydaje się, że badanie przestrzeni rotacyjnej jest również aktywnym obszarem badań. „Wykres rotacji drzew k-ary jest Hamiltonianem”, IPL 2008, dx.doi.org/10.1016/j.ipl.2008.09.013
Chad Brewbaker
38

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źć!

Suresh Venkat
źródło
Dzięki - to jest dobre! Przypomina mi inne problemy związane z „lokalizacją”. Czy faktycznie uważa się, że nie ma go w p?
Lev Reyzin
Nie wiem, czy rogatka jest bezpośrednio związana ze znanymi problemami złożoności. Istnieje jednak „niewłaściwy kierunek” w stosunku do faktoringu, polegający na tym, że problem z bramką może być sformułowany jako problem faktoringowy na odpowiednio wybranym wielomianu.
Suresh Venkat
1
Czy znane są mało prawdopodobne konsekwencje tego, że ten problem jest NP-zupełny, tak jak w przypadku izomorfizmu grafów (załamanie PH)?
Joshua Grochow
Nie, że jestem świadomy. nie badano go aż tak bardzo, szkoda, bo to takie naturalne.
Suresh Venkat
2
Podobny problem występuje w bioinformatyce: biorąc pod uwagę zestaw potencjalnie / miejmy nadzieję nakładających się, losowo utworzonych podciągów łańcucha znacznie dłuższych niż poszczególne elementy; obliczyć oryginalny ciąg. (sekwencjonowanie genów)
Raphael
38

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 a1,a2,,anb1,b2,,bn mniejsze niż, równe lub większe niżB:=iA:=iai ?B:=ibi

  • 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

Jeffε
źródło
3
Fajny, podoba mi się !!
Hsien-Chih Chang 張顯 之
Cóż, jeśli weźmiemy tylko 1000 losowych liczb całkowitych, niezbyt dużych, to istnieje około sposobów na podzielenie ich na dwa zestawy, więc spodziewałbym się, że dwie z tych sum znajdują się w obrębie 900 lub więcej bitów między sobą (i w połowie całkowitej sumy). Z drugiej strony, znalezienie „najgorszych” dwóch sekwencji do porównania z tych 2 999 możliwości jest również bardzo, bardzo trudne. 29992999
gnasher729,
30

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 PNPPNEXPEXPNEXPEXPNEXPPNEXP=EXP, co jest sprzeczne z naszym założeniem.) Istnieje wiele naturalnych problemów z kompletnością NEXP
Joshua Grochow
źródło
Podoba mi się ostatni przykład. Czy masz jakieś referencje na ten temat?
Marcos Villagra,
1
SR Mahaney. Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa. Journal of Computer and System Sciences 25: 130-143. 1982. dx.doi.org/10.1016/0022-0000(82)90002-2 Rzadkie zestawy w NP - P iff NEXP neq EXP: J. Hartmanis, N. Immerman, V. Sewelson, Rzadkie zestawy w NP-P: EXPTIME kontra NEXPTIME, Informacja i kontrola, Tom 65, Wydania 2-3, maj-czerwiec 1985, strony 158-181. dx.doi.org/10.1016/S0019-9958(85)80004-8
Joshua Grochow
To ładna lista, chociaż pierwsze trzy są dość podobne :) Podoba mi się również ostatni przykład.
Lew Reyzin
28

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

Eric Allender
źródło
24

Monotonia samo-dualność

Dla dowolnej funkcji boolowskiej f=f(x1,x2,...,xn) , to jest podwójnafd=f¯(x1¯,x2¯,...,xn¯) . Biorąc pod uwagę,f(x1,x2,...,xn)reprezentowane przez formułę CNF, musimy zdecydować, czy f=fd .

Problem ten występuje w ko-NP [ log2n ], tzn. Można go rozstrzygać o krokach niedeterministycznych O(log2n/loglogn) . Zatem ma on quasi-wielomianowy algorytm czasu (czas O(nlogn/loglogn) ), 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.

Danu
źródło
23

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.

Jeffε
źródło
1
Warto wspomnieć, że podobnie jak w przypadku wielu problemów potencjalnie pośrednich NP, znany jest niewielki wariant NP-zupełny. Mianowicie, 3-różnorodny rodzaj węzła jest NP-kompletny: biorąc pod uwagę zamknięty łańcuch wielokątny w trójkątnej 3-rozmaitości i liczbie całkowitej g, czy węzeł jest granicą powierzchni rodzaju co najwyżej g? (Bycie rozpiętym jest równoważne rodzajowi 0.) doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016
Joshua
Jest również zawarty w ko-AM (Hara, Tani, Yamamoto), więc nie w NPC, chyba że hierarchia wielomianowa się załamie.
Peter Shor,
3
Właściwie to wciąż jest otwarte. Tasos Sidiropoulos znalazł błąd w dowodzie Hara-Tani-Yamamoto.
Jeffε
Od czasu, ta odpowiedź jest po raz pierwszy opublikował, Kuperberg umieszcza go w warunku ogólnego Riemanna hipotezę i Lackenby umieszcza go unconditonally w c o N P . coNPcoNP
Mark S
19

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.

Matthias
źródło
Czy możesz podać referencje? Brzmi interesująco.
Joshua Grochow
1
M. Jurdziński. Decyzja o wygranej w grach parzystości jest w trybie UP \ cap co-Up. Listy przetwarzania informacji 68 (3): 119–124. 1998. Powinien być przynajmniej dobrym punktem wyjścia.
Matthias,
Niedawny artykuł „Algorytm pompowania dla ergodycznych stochastycznych gier o średniej wypłacie z doskonałymi informacjami” pokazuje również, że nawet uogólnienie gry parzystości można rozwiązać w czasie pseudo-wielomianowym. W szczególności pokazują, że gra o nazwie BWR ma algorytm pseudo-wielomianowy, gdy istnieje stała liczba „losowych węzłów”. Gra w parzystość ma miejsce, gdy nie ma losowych węzłów.
Danu,
Niedawno wykazano, że gry parzystości można rozwiązać w quasipolynomialnym czasie, patrz tutaj na przykład.
Thomas Klimpel
18

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).

Moritz
źródło
Tak, to był głupi komentarz, który zacząłem usuwać zaraz po opublikowaniu. Dziękuję Ci. :)
Daniel Apon
Dzięki! Ale chyba nie tyle myślałem o problemach z przybliżeniem, ale raczej o problemach naturalnych.
Lev Reyzin
Prawdopodobnie są to naturalne problemy, ponieważ odpowiadają temu, co można osiągnąć dzięki naturalnemu zestawowi technik, w tym przypadku programowaniu półfinałowemu.
Moritz
Myślę, że „naturalne” jest niejasnym kryterium ...
Lew Reyzin
18

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).no(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
András Salamon
źródło
17

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

Peter Shor
źródło
17

Wersja Pigeonhole Subset Sum (lub Subset Sum Equality).

Dany:

n

akZ>0
k=0n1ak<2n1

Zgodnie z zasadą szufladki muszą istnieć dwa rozłączne podzbiory, takie, że:S1,S2{1,,n}

jS1aj=kS2ak

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.

834
źródło
16

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.

Joe Fitzsimons
źródło
15

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ł an=2ka

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 wPk2kVTVPk12k1i>0Pk[2i1]Pk[2i]e ; niech P kTjeś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żywamyTPk1[i]=Pk[2i1]e=(Pk[2i1],Pk[2i])Pk1[i]=Pk[2i]PkT decyzją, które węzły (zwycięzcy) przechodzą do następnej rundy Pk1. Stąd, biorąc pod uwagę permutację na można faktycznie zdefiniować k rund P k - 1 , , P 02kkPk1,,P0 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.2k

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

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

Pytanie: czy zawiera (rozciągający się) dwumianowy arborescencję na 2 tysT2k 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.2kxa2k1x2k1yxyk=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.
virgi
źródło
13

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

Marcos Villagra
źródło
Należy podkreślić, że jest to klasa problemów związanych funkcyjnych w . NPcoNP
Marcos Villagra,
12

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.

Holger
źródło
2
Chociaż jest to interesujący wynik, jeśli sprawdzisz artykuł, powiesz nawet, że dowód pośredniej złożoności jest zasadniczo taki sam jak twierdzenie Ladnera, z tym wyjątkiem, że robisz to po przekątnej w wyborze ograniczenia LHS. Nie wiem więc, czy liczy się to jako „naturalny” problem, a nie tylko inne kodowanie twierdzenia Ladnera.
Joshua Grochow
Zauważ też, że są to ograniczenia typu źródło i cel. Cel (prawa strona) musi mieć specjalną formę, aby wymusić iniekcję.
András Salamon,
11

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.NPNP

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

Mohammad Al-Turkistany
źródło
czy masz odniesienie do definicji problemu?
Lew Reyzin
Odniesienie zostało dodane.
Mohammad Al-Turkistany
10

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

Suresh Venkat
źródło
10

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 β > 1nv1vβvβ>1 .

, problem jestNPCONPa 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β=nNPcoNPNPPββ=no(1/loglogn)NP

MCH
źródło
9

G=(V,E)fvVf(v)e=uvE|f(u)f(v)|f:V{0,1,2,,|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.
Oleksandr Bondarenko
źródło
9

PNPO(nlogn)NPNP

Mohammad Al-Turkistany
źródło
LOGNPNP[log2n]
8

abax+1b

γ

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

γRMM

RM={x,y:there is a string z such that on input x and guess z M has output y}

L1Σ1γL2Σ2L1γL2MxΣ1yΣ2x,yRMx,yRMxL1yL2MxxxL2xL1

Oleksandr Bondarenko
źródło
γ
6

PNPO(nlogn)

Mohammad Al-Turkistany
źródło
5

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)0GF(q)qr

p(x)=rx
p(x)rxrxr

deg(p)=0

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

Massimo Cafaro
źródło
4

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):

Thomas Klimpel
źródło
3

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
András Salamon
źródło
2

Problemem trudnym dla GI, o którym nie wiadomo, że jest NP-complete, może być WAGA_HYPERGRAPH_ISOMORPHISM. Dostajesz dwa hipergrrafysol1 i sol2) na n wierzchołki z ważonymi hiper-krawędziami decydują, czy istnieje permutacja wierzchołków π obrócenie sol1 w sol2). Zobacz także: Problem z trudnym grafem GI nie jest znanyN.P.-kompletny

użytkownik49753
źródło