Przykłady, w których znaczenie ma rozmiar alfabetu ( ) użyty do kodowania

Niech będzie alfabetem, czyli niepustym zbiorem skończonym. Łańcuch to dowolna skończona sekwencja elementów (znaków) z . Na przykład to alfabet binarny, a to ciąg znaków dla tego alfabetu.$\Sigma$$\Sigma$$\{0, 1\}$$0110$

Zazwyczaj, dopóki zawiera więcej niż 1 element, dokładna liczba elementów w nie ma znaczenia: w najlepszym razie otrzymujemy gdzieś inną stałą. Innymi słowy, tak naprawdę nie ma znaczenia, czy użyjemy binarnego alfabetu, liczb, alfabetu łacińskiego czy Unicode.$\Sigma$$\Sigma$

Czy istnieją przykłady sytuacji, w których ma znaczenie wielkość alfabetu?

Interesuje mnie to, ponieważ natknąłem się na jeden taki przykład:

Dla każdego alfabetu definiujemy losową wyrocznię jako wyrocznię, która zwraca losowe elementy z , tak że każdy element ma równą szansę na zwrot (więc szansa na każdy element to ).$\Sigma$$O_{\Sigma}$$\Sigma$$\frac{1}{|\Sigma|}$

W przypadku niektórych alfabetów i - być może różnych rozmiarów - rozważ klasę maszyn Oracle z dostępem do . Interesują nas maszyny Oracle w tej klasie, które zachowują się tak samo jak . Innymi słowy, chcemy przekształcić wyrocznię w wyrocznię za pomocą maszyny Turinga. Taką maszynę Turinga nazwiemy programem konwersji.$\Sigma_1$$\Sigma_2$$O_{\Sigma_1}$$O_{\Sigma_2}$$O_{\Sigma_1}$$O_{\Sigma_2}$

Niech i . Przekształcanie w wyrocznię jest łatwe: dwukrotnie , konwertując wyniki w następujący sposób: , , , . Oczywiście ten program działa w czasie .$\Sigma_1 = \{ 0, 1 \}$$\Sigma = \{ 0, 1, 2, 3 \}$$O_{\Sigma_1}$$O_{\Sigma_2}$$O_{\Sigma_1}$$00 \rightarrow 0$$01 \rightarrow 1$$10 \rightarrow 2$$11 \rightarrow 3$$O(1)$

Teraz pozwól i . Dla tych dwóch języków wszystkie programy konwersji działają w czasie , tzn. Nie ma programów konwersji od do które działają w czasie .$\Sigma_1 = \{ 0, 1 \}$$\Sigma = \{ 0, 1, 2 \}$$O(\infty)$$O_{\Sigma_1}$$O_{\Sigma_2}$$O(1)$

Można to udowodnić przez sprzeczność: załóżmy, że istnieje program do konwersji z na działający w czasie . Oznacza to, że istnieje takie że wykonuje co najwyżej zapytania do .$C$$O_{\Sigma_1}$$O_{\Sigma_2}$$O(1)$$d \in \mathbb{N}$$C$$d$$\Sigma_1$

$C$ może wykonać mniej niż zapytań w niektórych ścieżkach wykonania. Możemy łatwo zbudować program konwersji który wykonuje , śledząc ile razy zostało wykonane zapytanie Oracle. Niech będzie liczbą zapytań wyroczni. następnie wykonuje dodatkowe zapytania wyroczni, odrzucając wyniki, zwracając to, co by zwrócił.$d$$C'$$C$$k$$C'$$d-k$$C$

W ten sposób istnieją dokładnie ścieżki wykonawcze dla . Dokładnie z tych dróg realizacji spowoduje powrotem . Jednak nie jest liczbą całkowitą, więc mamy sprzeczność. Dlatego nie istnieje żaden taki program.$|\Sigma_1|^d = 2^d$$C'$$\frac{1}{|\Sigma_2|} = \frac{1}{3}$$C'$$0$$\frac{2^d}{3}$

Mówiąc bardziej ogólnie, jeśli mamy alfabety i z i , wówczas istnieje program do konwersji z na wtedy i tylko wtedy, gdy wszystkie liczby pierwsze występujące w rozkładzie na czynniki pierwsze pojawiają się również w rozkładzie na czynniki pierwsze (więc wykładniki liczb pierwszych w rozkładzie na czynniki pierwsze nie mają znaczenia).$\Sigma_1$$\Sigma_2$$|\Sigma_1|=n$$|\Sigma_2|=k$$O_{\Sigma_1}$$O_{\Sigma_2}$$n$$k$

Konsekwencją tego jest to, że jeśli mamy generator liczb losowych generujący ciąg binarny o długości , nie możemy użyć tego generatora liczb losowych do wygenerowania liczby w z dokładnie takim samym prawdopodobieństwem.$l$$\{0, 1, 2\}$

Wymyśliłem powyższy problem, stojąc w supermarkecie i zastanawiając się, co zjeść na obiad. Zastanawiałem się, czy mógłbym użyć rzutów monetą, aby zdecydować między wyborem A, B i C. Jak się okazuje, jest to niemożliwe.

Istnieje kilka przykładów formalnej teorii języka, w których 2-znakowe i 3-znakowe alfabety dają jakościowo różne zachowania. Kozen podaje następujący ładny przykład (parafrazowany):

Niech alfabet będzie = {1, .., k} ze standardowym porządkiem numerycznym i zdefiniuj sort (x) jako permutację słowa x, w którym litery x pojawiają się w uporządkowanej kolejności. Rozszerz sort (A) = {sort (x) | x A} i rozważ następujące oświadczenie:$\Sigma$$\in$

Jeśli A jest pozbawione kontekstu, to sort (A) jest pozbawione kontekstu.

To twierdzenie jest prawdziwe dla k = 2, ale fałszywe dla k 3.$\ge$

Dowód Dinura na twierdzenie PCP w dużej mierze opiera się na manipulacji wielkością alfabetu.

W szczególności ogólna struktura dowodu jest iteracyjnym zastosowaniem techniki zasilania grafu logarytmem w liczbie razy wykresu. Na każdej iteracji wykres jest wstępnie przetwarzany na zwykły wykres rozwijany, wzmacniany przez moc (która wysadza rozmiar alfabetu), a następnie stosuje się kompozycję PCP (zamieniając każde ograniczenie na duży alfabet w system ograniczeń na mały alfabet).

Domyślnym celem tego procesu jest znalezienie sposobu na ponowne użycie etapu amplifikacji, dopóki wartość UNSAT nie stanie się stałą ułamkiem (potwierdzającym twierdzenie PCP). Kluczową kwestią jest to, że o ile rozmiar alfabetu nie zostanie za każdym razem cofnięty, wynikowy wykres nie jest potrzebny do ostatecznej redukcji.

Wymagania twojego przykładu są dość surowe. Jeśli się rozluźnisz, wymagaj tylko, aby konwersja działała w w oczekiwaniu . Możliwe jest równomierne próbkowanie z przy użyciu, w oczekiwaniu, stałej liczby rzutów monetą.$O(1)$$\{0,1,2\}$

Nie jestem ekspertem w tej dziedzinie, ale jednym dobrym przykładem jest to, że rozmiar alfabetu ma znaczenie, to kodowanie i zwięzłe struktury danych. Wyobraź sobie, że chcesz przedstawić wiadomość nad alfabetem w alfabecie (np. Aby zapisać ją na komputerze binarnym). Chcesz zminimalizować wymaganą przestrzeń, ale jednocześnie chcesz móc szybko odczytywać i zapisywać poszczególne znaki wiadomości (powiedzmy w ). Tego typu problemy były badane już od dłuższego czasu. Ostatni artykuł Dodisa, Patrascu i Thorupa na ten temat oraz odnośniki do niego powinny być dobrym punktem wyjścia.$\{0,1,2\}$$\{0,1\}$$O(1)$

W przypadku kodów korygujących błędy możliwe jest, że istnieje zasadnicza różnica między kodami binarnymi i kodami w porównaniu z większymi alfabetami, ponieważ niektórzy uważają, że przykłady Gilberta Varshamova dla kodów korygujących ułamek błędów (które są zasadniczo chciwymi lub przypadkowymi przykładami) być ciasne w przypadku binarnym i wiadomo, że nie są ciasne w stosunku do dużego alfabetu za pomocą kodów geometrii algebraicznej. Doprowadziło to niektórych do spekulacji, że standardowa definicja kodów korekcji błędów dla dużego alfabetu nie jest właściwą analogią kodów binarnych korekcji błędów.

W moich własnych badaniach napotkałem interesujący przypadek niewielkich różnic w wielkości alfabetu, dających radykalne różnice w wynikowej teorii. Szorstki opis problemu uczenia obwodów probabilistycznych jest następujący: uczący się może przesłonić bramy ukrytej obwodzie i obserwować powstałego wyjście, a celem jest stworzenie „funkcjonalnie równoważny” obwodu. W przypadku obwodów boolowskich, ilekroć bramka ma „wpływ” na wyjście, można odizolować wpływową ścieżkę od tej bramki do wyjścia obwodu. W przypadku obwodów o wielkości alfabetu nie ma to już miejsca - mianowicie istnieją obwody, które mają bramki mające duży wpływ na wartość wyjściową, ale nie wpływają na żadną ścieżkę do wyjścia! Ten wynik był dość zaskakujący.$\ge 3$

Wynik jest nieco techniczny, ale jeśli jesteś zainteresowany, możesz porównać Lemma 8 z Sekcją 4.1 dla odpowiednich twierdzeń twierdzeń.