Hipoteza Bermana-Hartmanisa
Czy istnieje wielomianowy izomorfizm czasowy między każdymi dwoma językami NP-zupełnymi?
W teorii złożoności strukturalnej hipoteza Bermana – Hartmanisa jest nierozwiązaną hipotezą nazwaną na cześć Leonarda C. Bermana i Jurisa Hartmanisa , która stwierdza, że wszystkie języki NP-zupełne wyglądają podobnie w tym sensie, że można je ze sobą powiązać wielomianowymi izomorfizmami czasu .
Oświadczenie
Izomorfizm między językami formalnymi L 1 i L 2 jest bijektywną mapą f od ciągów w alfabecie L 1 do ciągów w alfabecie L 2 , z tą właściwością, że ciąg x należy do L 1 wtedy i tylko wtedy, gdy f ( x ) należy do L 2 . Jest to wielomianowy izomorfizm czasowy (lub w skrócie izomorfizm p ), jeśli zarówno f , jak i jej funkcja odwrotna mogą być obliczone w ilości wielomianu czasowego długości ich argumentów.
Berman i Hartmanis (1977) zauważyli, że wszystkie języki znane w tamtym czasie jako NP-zupełne były p -izomorficzne. Co więcej, zaobserwowali, że wszystkie znane wówczas języki NP-zupełne były dopełniane i udowodnili (analogicznie do twierdzenia o izomorfizmie Myhilla ), że wszystkie pary języków NP-zupełnych z możliwością dopełniania są p -izomorficzne. Język L jest uzupełnialny , jeśli istnieje wielomianowa funkcja czasowa f ( x , y ) z odwrotnością wielomianu w czasie i z właściwością, że dla wszystkich x i y x należy do L wtedy i tylko wtedy, gdy należy f ( x , y ) do L : to znaczy, możliwe jest wypełnienie wejścia x nieistotną informacją y w sposób odwracalny, bez zmiany jego przynależności do języka. Na podstawie tych wyników Berman i Hartmanis przypuszczali, że wszystkie języki NP-zupełne są p -izomorficzne.
Ponieważ izomorfizm p zachowuje możliwość dopełniania i istnieją języki NP-zupełne, które można dopełniać, równoważnym sposobem wyrażenia hipotezy Bermana-Hartmanisa jest to, że wszystkie języki NP-kompletne są uzupełnialne. Izomorfizm czasu wielomianowego jest relacją równoważności i można go użyć do podziału języków formalnych na klasy równoważności , więc innym sposobem wyrażenia hipotezy Bermana-Hartmanisa jest to, że języki NP-zupełne tworzą pojedynczą klasę równoważności dla tej relacji.
Implikacje
Jeśli hipoteza Bermana-Hartmanisa jest prawdziwa, natychmiastową konsekwencją byłby nieistnienie rzadkich języków NP-zupełnych, a mianowicie języków, w których liczba przypadków tak o długości n rośnie tylko wielomianowo jako funkcja n . Znane języki NP-zupełne mają liczbę instancji tak, która rośnie wykładniczo, a jeśli L jest językiem z wykładniczo wieloma przypadkami tak, to nie może być p -izomorficzny z rzadkim językiem, ponieważ jego instancje tak musiałyby być mapowane na ciągi, które są dłuższe niż wielomian, aby odwzorowanie było jeden do jednego.
Nieistnienie rzadkich języków NP-zupełnych z kolei implikuje, że P ≠ NP , ponieważ jeśli P = NP, to każdy nietrywialny język w P (w tym niektóre rzadkie, takie jak język ciągów binarnych, których wszystkie bity są zerowe) byłby NP -kompletny. W 1982 roku Steve Mahaney opublikował swój dowód, że nieistnienie rzadkich języków NP-zupełnych (z NP-zupełnością zdefiniowaną w standardowy sposób przy użyciu redukcji wielu-jeden ) jest w rzeczywistości równoważne stwierdzeniu, że P ≠ NP; to jest twierdzenie Mahaneya . Nawet w przypadku luźnej definicji NP-zupełności przy użyciu redukcji Turinga istnienie rzadkiego języka NP-zupełności oznaczałoby nieoczekiwany upadek hierarchii wielomianów .
Dowód
0 Jako dowód na przypuszczenie, Agrawal et al. (1997) wykazali, że analogiczne przypuszczenie z ograniczonym rodzajem redukcji jest prawdziwe: każde dwa języki, które są kompletne dla NP pod AC 0 wiele jeden redukcji mają izomorfizm AC. Agrawal i Watanabe (2009) wykazali, że jeśli istnieją funkcje jednokierunkowe , których nie można odwrócić w czasie wielomianowym na wszystkich wejściach, ale jeśli każda taka funkcja ma mały, ale gęsty podzbiór danych wejściowych, na których można ją odwrócić w P/poly (jak to jest prawdą dla znanych funkcji tego typu), to co dwa języki NP-zupełne mają izomorfizm P/poli. A Fenner, Fortnow i Kurtz (1992) znaleźli model maszyny wyroczni , w którym odpowiednik hipotezy izomorfizmu jest prawdziwy.
Dowody przeciwko temu przypuszczeniu dostarczyli Joseph & Young (1985) oraz Kurtz, Mahaney & Royer (1995) . Joseph i Young wprowadzili klasę problemów NP-zupełnych, zbiory k -twórcze , dla których nie jest znany żaden p -izomorfizm ze standardowymi problemami NP-zupełnymi. Kurtza i in. pokazał, że w modelach maszyn wyroczni, które mają dostęp do losowej wyroczni , analogia hipotezy nie jest prawdziwa: jeśli A jest losową wyrocznią, to nie wszystkie zbiory kompletne dla NP A mają izomorfizmy w PA . Losowe wyrocznie są powszechnie używane w teorii kryptografii do modelowania kryptograficznych funkcji skrótu , które są obliczeniowo nie do odróżnienia od przypadkowych, a konstrukcja Kurtza i in. można pełnić taką funkcję zamiast wyroczni. Między innymi z tego powodu wielu teoretyków złożoności uważa hipotezę izomorfizmu Bermana – Hartmanisa za fałszywą.