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

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?

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 .

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 Graph$P$

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 $P$$P$$P$

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 ( $\sf NP\cap coNP$n$e^{O(\sqrt{n})}$$n$$\sf P$