Przykład, w którym równoważność jest łatwa, ale znalezienie reprezentanta klasy jest trudne

Załóżmy, że mamy klasę obiektów (np. Wykresy, ciągi) i relację równoważności tych obiektów. W przypadku wykresów może to być izomorfizm wykresów. W przypadku ciągów moglibyśmy zadeklarować dwa równoważne ciągi, jeśli są one wzajemnie anagramami.

Jestem zainteresowany obliczeniem przedstawiciela dla klasy równoważności. To znaczy, chcę funkcję f () taką, że dla dowolnych dwóch obiektów x, y, f (x) = f (y) iff x i y są równoważne. (*)

Na przykład anagramów, f (s) może sortować litery w ciągu, tj. f („cabac”) = „aabcc”. W przypadku izomorfizmu grafów możemy przyjąć, że f (G) jest wykresem G ', który jest izomorficzny w stosunku do G i jest pierwszym leksykorficznym wykresem posiadającym tę właściwość.

Teraz pytanie: czy istnieje przykład, w którym problem ustalenia, czy dwa elementy są równoważne, jest „łatwy” (rozwiązany w czasie wielorakim), podczas gdy znalezienie reprezentatywnego jest trudne (tzn. Nie ma algorytmu obliczania czasu f (), który spełnia ( *)).

Ok, a co powiesz na: liczby i są równoważne, jeśli albo , albo oba i mają faktoryzacje i gdzie , i są wszystkie pierwsze, a . To znaczy: produkty dwóch liczb pierwszych są równoważne, gdy dzielą ich najmniejszy czynnik pierwszy; inne liczby są sobie równe.$x$$y$$x=y$$x$$y$$x=pq$$y=pr$$p$$q$$r$$p < \min(q,r)$

Łatwo jest sprawdzić, czy dwie różne liczby są równoważne: obliczyć ich gcd, przetestować, czy nie jest to łatwe, przetestować, czy gcd jest mniejszy niż kofaktory i przetestować, czy wszystkie gcd i jego kofaktory są pierwsze.

Ale nie jest oczywiste, jak obliczyć funkcję reprezentatywną czasie wielomianowym, a jeśli dodasz wymóg, że musi być równoważny to każda funkcja reprezentatywna pozwoliłaby nam na uwzględnienie większości produktów dwóch liczb pierwszych (każda, która nie jest to jego własny przedstawiciel).f ( x ) $f$$f(x)$$x$

Dwie liczby całkowite mod są równoważne, jeśli mod . Jeśli można łatwo obliczyć przedstawiciela klasy dla tej funkcji, faktoryzację można przeprowadzić w probabilistycznym czasie wielomianowym.n x 2 ≡ y 2$x,y$$n$$x^{2} \equiv y^{2}$$n$

Ogólnie taki przykład sugerowałby, że . Załóżmy, że jest relacją równoważności, która jest rozstrzygalna w czasie wielomianowym. Następnie, poprzez wyszukiwanie leksykograficzne przy użyciu wyroczni , można znaleźć najmniej leksykograficzny element w klasie równoważności dowolnego łańcucha. Jeśli , staje się to czasem wielomianowym, więc możesz użyć leksykograficznie najmniej równoważnego łańcucha jako reprezentanta klasy. Ta obserwacja jest pierwotnie spowodowana przez Blassa i Gurewicza [1].R N P P = N $P \neq NP$$R$$NP$$P=NP$

Taki przykład sugerowałby także (a zatem w szczególności ).P ≠ U $UP \not\subseteq BQP$$P \neq UP$

Pytanie, które zadałeś, jest dokładnie tym, co oznaczaliśmy w naszym artykule z Lance Fortnow [2]. Ten artykuł zawiera również wyniki, które tu przedstawiłem, a także przykład funkcji skrótu wskazanych przez Petera Shora, kilka innych możliwych przykładów oraz powiązane wyniki i pytania.$PEq =? Ker(FP)$

[1] Blass, A. i Gurevich, Y. Relacje równoważności, niezmienniki i formy normalne . SIAM J. Comput. 13 (4): 682–689, 1984.

[2] Fortnow, L. i Grochow, JA ponownie omówiono klasy złożoności problemów równoważności . Poinformować. i Comput. 209 (4): 748–763, 2011. Dostępne również na arxiv .

Czy „przedstawiciel” musi należeć do klasy równoważności?

Jeśli tak, weź jakąkolwiek kryptograficznie silną funkcję skrótu o odporności na kolizję.$f$

Niech jeśli . Łatwo jest sprawdzić, czy dwie rzeczy są równoważne, ale jeśli biorąc pod uwagę , można znaleźć kanoniczne preimage , to można znaleźć dwa łańcuchy i takie, że . To ma być trudne (to właśnie oznacza odporność na kolizje).f ( x ) = f ( y $x \simeq y$$f(x) = f(y)\,$h x y f ( x ) = f ( y $f(x) = h$$h$$x$$y$$f(x)=f(y)\,$

Oczywiście informatycy nie mogą udowodnić, że istnieją kryptograficznie silne funkcje skrótu z odpornością na zderzenia, ale mają wielu kandydatów.

Po pierwsze, to, o co tak naprawdę prosisz, nazywa się zwykle niezmiennikiem. Forma kanoniczna lub normalna wymaga również, aby był równoważny dla wszystkich . (Pytanie o „przedstawiciela” jest nieco dwuznaczne, ponieważ niektórzy autorzy mogą oznaczać, że obejmuje to warunek formy kanonicznej).$f(x)$$x$$x$

Po drugie, proszę wybaczyć bezwstydną autopromocję, ale to jest dokładnie jedno z pytań, nad którymi pracowaliśmy z Fortnow [1]. Pokazaliśmy, że jeśli każda relacja równoważności, o której można zadecydować w ma również całkowitą niezmienność w , to zdarzają się złe rzeczy. W szczególności oznaczałoby to . Jeśli obowiązuje obietnica w wersji tego oświadczenia (patrz Twierdzenie 4.6), to i .$\mathsf{P}$$\mathsf{FP}$$\mathsf{UP} \subseteq \mathsf{BQP}$$\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$$\mathsf{PH} = \mathsf{AM}$

Teraz, jeśli naprawdę chcesz postaci kanonicznej (reprezentanta każdej klasy równoważności, która również należy do klasy równoważności), pokazujemy, że dzieje się jeszcze gorzej. Oznacza to, że jeśli każda relacja równoważności rozstrzygalna w czasie wielomianowym ma postać kanoniczną wielomianową, to:

• Liczby całkowite mogą być uwzględniane w probabilistycznym czasie wieloczynnościowym
• Bezkolizyjne funkcje skrótu, które można ocenić w , nie istnieją.$\mathsf{FP}$
• $\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (stąd )$\mathsf{PH} = \mathsf{BPP}$

Istnieją również wyrocznie idące w obie strony dla większości tych stwierdzeń na temat relacji równoważności, zarówno nam, jak i Blassowi i Gurewiczowi [2].

Jeśli zamiast „dowolnego” przedstawiciela, poprosisz o element leksykograficznie najmniejszy w klasie równoważności, znalezienie najmniejszego elementu leksykograficznego w klasie równoważności może być twarde (w rzeczywistości -twarde) - nawet jeśli związek ma postać kanoniczną o czasie wielomianowym [2].$NP$$P^{NP}$

[1] Lance Fortnow i Joshua A. Grochow. Ponownie omówiono klasy złożoności problemów równoważności . Poinformować. i Comput. 209: 4 (2011), 748–763. Dostępny również jako arXiv: 0907.4775v2 .

[2] Andreas Blass i Jurij Gurewicz. Relacje równoważności, niezmienniki i formy normalne . SIAM J. Comput. 13: 4 (1984), 24–42.

Oto próba innej odpowiedzi, w której poluzowujemy wymóg dotyczący „przedstawiciela”; w rzeczywistości nie musi to być członek klasy równoważności, ale tylko funkcja identyfikująca klasę równoważności.

Załóżmy, że masz grupę, w której możesz przeprowadzać testy członkostwa w podgrupach. To znaczy, biorąc pod uwagę , możesz sprawdzić, czy znajduje się w podgrupie wygenerowanej przez . h g 1 , … , g $g_1, g_2, \ldots, g_k$$h$$g_1, \ldots, g_k$

Weź swoje klasy równoważności jako zestawy elementów które generują tę samą podgrupę. Łatwo jest sprawdzić, czy dwa zestawy generują tę samą podgrupę. Jednak nie jest wcale jasne, jak znaleźć unikalny identyfikator dla każdej podgrupy. Podejrzewam, że to naprawdę przykład, jeśli zakładasz grupy czarnych skrzynek z testami członkostwa w podgrupach. Jednak nie wiem, czy jest jakaś grupa, która nie jest wyrocznią, w której problem wydaje się być trudny.$g_1, g_2, \ldots, g_k$

Oto wymyślony przykład. Obiektami są pary których jest wzorem SAT, a jest proponowanym przypisaniem do zmiennych. Powiedz jeśli i albo (a) i są zadaniami spełniającymi, lub (b) i są zadaniami zadowalającymi. Jest to zwrotne, symetryczne i przechodnie. Każda niezadowalająca ma jedną klasę równoważności składającą się ze wszystkich . Każdy zadowalający ma klasę wszystkich gdzie$(H,X)$$H$$X$$(H,X) \sim (H',X')$$H=H'$$X$$X'$$X$$X'$$H$$(H,X)$$H$$(H,X)$$X$ jest zadowalającym zadaniem, a kolejna klasa z tymi niezadowalającymi.

Sprawdzanie, czy jest proste, gdyż po prostu sprawdzić, czy , a następnie, jeśli spełnia , a następnie, jeśli spełnia . Ale aby obliczyć element kanoniczny danej klasy z spełnionym przez$(H,X) \sim (H',X')$$H=H'$$X$$H$$X'$$H$$(H,X)$$H$$X$wydaje się zbyt trudne (nie jestem pewien, jak najlepiej udowodnić twardość). Możemy łatwo umieścić dodatkowe rozwiązanie dla instancji SAT, więc znajomość jednego rozwiązania zasadniczo nie pomoże nam znaleźć żadnego innego rozwiązania, nie mówiąc już o wyborze rozwiązania kanonicznego. (Edycja: Mam na myśli to, że nie oczekuję wydajnego algorytmu znajdowania dodatkowych rozwiązań przy pierwszym rozwiązaniu. Ponieważ moglibyśmy go użyć do rozwiązania problemów SAT, najpierw „zasadzając” dodatkowe rozwiązanie problemu, a następnie karmiąc go algorytm. Zobacz komentarze.)

To pytanie otwarte, przynajmniej w przypadku wykresów. Uważam, że najnowszy postęp

Babai i Kucera, „Kanoniczne etykietowanie wykresów w średnim czasie liniowym”, FOCS, 1979

który daje (oczekiwany) liniowy algorytm czasu dla wykresu kanonicznego, który jest poprawny z prawdopodobieństwem$1 - \frac{1}{2^{O(n)}}$

Możesz przeczytać więcej na Wikipedii . Zauważ, że zdegenerowana wersja algorytmu Babai oznaczałaby, że nie ma takiego przykładu dla grafów.

Testowanie, czy dwa obwody o rozmiarze są równoważne.$\leq N$

Aby ustalić, czy , musisz ocenić tylko w punktach wejściowych. Aby określić przedstawiciela klasy, prawdopodobnie należałoby przetestować wszystkie możliwe obwody . Dla odpowiednio dużej jest to wykładniczo trudniejsze niż testowanie równoważności obwodu.$C_1 \sim C_2$$2^n$$2^{\Omega(N \log N)}$$N$

Słynny przykład z opisowej teorii zbiorów:

Zdefiniujmy relację równoważności na przez $\sim$$\mathbb R$

Jest to raczej „łatwa” relacja równoważności, w szczególności jest mierzalna.

Ale znalezienie przedstawicieli sprowadza się do znalezienia zbioru Vitali , który wymaga Aksjomatu Wyboru i nie może być mierzalny.

Niech obiekty we wszechświecie będą potrójnymi ( gdzie będzie problemem satysfakcji, dla zmiennych , jest albo 0 albo 1, a jest a łańcuch bitów o długości , gdzie . Oznacza to, że jest przypisaniem do który spełnia jeśli wynosi 1 lub nie spełnia jeśli wynosi 0. $\Phi, b, i)$$\Phi$$x_0, \ldots, x_{k-1}$$b$$i$$k$$\Phi(i)=b$$i$$x_0, \ldots, x_k$$\Phi$$b$$\Phi$$b$

Dwa obiekty są równoważne, jeśli mają takie same . Łatwy do sprawdzenia.$\Phi$

Niech reprezentatywny obiekt będzie największym leksykograficznie ze wszystkich w klasie równoważności.

Przedstawiciel jest NP-kompletny do znalezienia: rozwiązałby SAT, ponieważ jeśli największy leksykograficznie ma , to jest niezadowalająca; jeśli ma , jest zadowalające.$b=0$$\Phi$$b=1$

Wydaje się, że większość problemów NP-zupełnych można postawić w ten sposób; chodzi o umieszczenie certyfikatu członkostwa w kodowaniu elementu.

Pomyślałem, że może to był problem z pracą domową, dlatego wcześniej nie opublikowałem rozwiązania. Powinienem był to zrobić; Mógłbym wykorzystać te punkty, które dostał @ David-Eppstien. Dobroć wie, że ich nie potrzebuje.

Podejrzewam, że możesz to łatwo osiągnąć praktycznie dla każdego opisanego rodzaju problemu.

Trywialny przykład: Załóżmy, że obiekty są łańcuchami, a każdy jest równoważny tylko samemu sobie. Ustalenie, czy dwa elementy są równoważne, jest zawsze łatwe (to po prostu równość). Można jednak zdefiniować jako ulubioną funkcję twardego wstrzykiwania.f ( $x$$f()$