Problemy domniemane, ale nie udowodnione, że są łatwe

12

Mamy wiele problemów, takich jak rozkładanie na czynniki, które są wysoce domniemane, ale nie udowodnione, że znajdują się poza P. Czy są jakieś pytania o przeciwnych właściwościach, a mianowicie, że są one silnie przypuszczone, ale nie udowodniono, że znajdują się w P?

Elliot Gorokhovsky
źródło
Prośba o referencje, taka jak Twoja, jest zbyt szeroka dla Stack Exchange - poprosisz o ankietę całego obszaru badań! Musisz znacznie zawęzić koncentrację, zanim pojawi się pytanie o rozsądnym zakresie. Spróbuj porozmawiać ze swoim doradcą (doradcami), wyszukaj w Google Scholar i zapoznaj się z tym przewodnikiem, aby uzyskać lepsze (ponowne) wyszukiwania w Academia .
Raphael
Nie mamy ścisłej polityki dotyczącej pytań z listy, ale istnieje ogólna niechęć . Proszę zwrócić uwagę również na i dyskusję; możesz poprawić swoje pytanie, aby uniknąć opisanych tam problemów. Jeśli nie jesteś pewien, jak poprawić swoje pytanie, może pomożemy Ci na czacie z informatyki ?
Raphael
Masz na myśli problemy, w których nikt nie wie, czy są w P, czy poza nim?
Trilarion,
1
Takie problemy występują w niektórych podklasach wykresów; Spróbuję dodać odpowiedź później.
Juho,
@Juho Chciałbym zobaczyć twoją odpowiedź
Elliot Gorokhovsky,

Odpowiedzi:

22

Dwie dekady temu jedną z możliwych odpowiedzi byłoby testowanie pierwotności : istniały algorytmy działające w losowym czasie wielomianowym oraz algorytmy działające w deterministycznym czasie wielomianowym zgodnie z prawdopodobną hipotezą liczbową, ale nie są znane deterministyczne algorytmy czasu wielomianowego. W 2002 roku zmieniło się to wraz z przełomowym wynikiem Agrawala, Kayala i Saxeny, że testowanie pierwotności znajduje się w P. Więc nie możemy już używać tego przykładu.

Umieściłbym testowanie tożsamości wielomianowej jako przykład problemu, który ma duże szanse na bycie w P, ale gdzie nikt nie był w stanie tego udowodnić. Znamy losowe algorytmy wielomianowe do testowania tożsamości wielomianowej, ale brak algorytmów deterministycznych. Istnieją jednak wiarygodne powody, by sądzić, że algorytmy randomizowane mogą zostać poddane derandomizacji.

Na przykład w kryptografii mocno wierzy się, że istnieją wysoce bezpieczne generatory pseudolosowe (np. AES-CTR jest jednym rozsądnym kandydatem). A jeśli to prawda, to wielomianowe testowanie tożsamości powinno odbywać się w P. (Na przykład, użyj ustalonego nasienia, zastosuj generator pseudolosowy i użyj jego wyniku zamiast losowych bitów; zajęłoby to ogromny spisek, aby to się nie powiodło. ) Można to sformalizować za pomocą modelu losowej wyroczni; jeśli mamy funkcje skrótu, które można odpowiednio modelować za pomocą losowego modelu Oracle, oznacza to, że istnieje deterministyczny algorytm czasu wielomianowego do testowania tożsamości wielomianowej.

Aby uzyskać więcej informacji na temat tego argumentu, zobacz także moją odpowiedź na powiązany temat i moje komentarze na powiązane pytanie .

DW
źródło
12

To trudne pytanie, ponieważ nie ma konsensusu. Nadal są ludzie, którzy przypuszczają, że .P=NP

Ale moim zdaniem, najbardziej znaczącym problemem z istotnym przypuszczeniem, że jest on w to Isomorphism GraphP

Ale znowu nikt tak naprawdę nie wie.

Ogólnie rzecz biorąc, „przypuszczenie, że jest w ”, będzie rzadkością. Przypuszczamy, że problem występuje w jeśli nie mamy już dla niego algorytmu wielomianowego czasu. Jednak niemożność znalezienia algorytmu po tych wszystkich latach prawdopodobnie będzie postrzegana bardziej jako „dowód”, że problem jest trudny, a nie łatwy.P PPPP

jmite
źródło
Myślałem, że izomorfizm grafów jest ciasno osadzony w bliskim sąsiedztwie NP-C?
John Dvorak,
1
@JanDvorak mathoverflow.net/questions/223420/…
xavierm02
Jako niewielkie uogólnienie, nawet grupowy izomorfizm nie występuje w ! wiadomo, że jest co najwyżej quasipolynomial, tak jak obecnie jest izomorfizm grafów (dzięki Babai). P
wchargin
4

Chociaż nie jestem nawet blisko ekspertem w tej dziedzinie, przypuszczam, że problem z rozłączaniem uważa się za P. Znany jest z i istnieją dla niego algorytmy podwykładnicze . Mówiąc dokładniej, istnieje algorytm, który działa , gdzie jest liczbą skrzyżowań, patrz tutaj . Należy zauważyć, że inna odpowiedź wskazuje również wiarę w unknotting problemu leżącego w .e O ( NPcoNPnP.eO(n)nP

Wojowu
źródło
1
Jakie są dowody / powody, by sądzić, że problem rozpinania powinien być w P? Istnieje wiele problemów w NP coNP, które mają algorytmy czasu podwykładniczego, ale uważa się, że prawdopodobnie nie są w P, więc jeśli są to jedyne istotne fakty, wydaje się to dość słaby powód, aby sądzić, że tak powinno być w P. jest bardzo daleko od wielomianu. e en
DW
@DW Czy możesz podać przykład takiego problemu, który może występować poza P? Nie znam żadnego.
Wojowu
2
Pewnie: faktoring, dyskretny log. Lub znalezienie przybliżonej równowagi Nasha w grze dwuosobowej i innych (patrz ten komentarz Scott Aaronson ). Lub GapCVP , wersja luki problemu najbliższego wektora dla sieci, z odpowiednimi parametrami.
DW
1
en.wikipedia.org/wiki/… : „Wiadomo, że jest zarówno w NP, jak i w NP. Jest tak, ponieważ [...]”
DW
1
@DW Ach, to prawda. Widzę teraz, jak to unieważnia moją odpowiedź. Myślę, że i tak to zostawię, ale dziękuję za wyjaśnienie!
Wojowu