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

9

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.ΣΣ{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.ΣΣ

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 ).ΣOΣΣ1|Σ|

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.Σ1Σ2OΣ1OΣ2OΣ1OΣ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 .Σ1={0,1}Σ={0,1,2,3}OΣ1OΣ2OΣ1000011102113O(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 .Σ1={0,1}Σ={0,1,2}O()OΣ1OΣ2O(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 .COΣ1OΣ2O(1)dNCdΣ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ł.dCCkCdkC

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.|Σ1|d=2dC1|Σ2|=13C02d3

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).Σ1Σ2|Σ1|=n|Σ2|=kOΣ1OΣ2nk

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.

Alex ten Brink
źródło
5
Dowód Dinura na twierdzenie PCP opiera się w dużej mierze na manipulowaniu wielkością alfabetu, a konkretnie wysadzeniu go w powietrze, a następnie kilkakrotnym zmniejszeniu go przez kompozycję PCP. Bez drugiego fragmentu kroku (z powrotem zmniejszając rozmiar alfabetu) dowód nie działa.
Daniel Apon,
2
@Daniel Apon: Dlaczego nie przesłać ponownie jako odpowiedzi?
Joshua Grochow
@Joshua, ups. Pewnie. :)
Daniel Apon,

Odpowiedzi:

11

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:Σ

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.

mikero
źródło
11

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.

Daniel Apon
źródło
9

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)

Matthias
źródło
8

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.

Gil Kalai
źródło
5

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.3

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

Lew Reyzin
źródło
To wydaje się bardzo interesujące. Czy próbowałeś zmodyfikować definicję wpływu, aby zobaczyć, czy możesz uzyskać coś podobnego do przypadku logicznego?
Kaveh
Nasza definicja wpływu jest dość naturalna - patrzysz na rozkład prawdopodobieństwa węzła wyjściowego przy różnych ustawieniach celu. Jeśli wszystkie ustawienia dają taki sam dokładny rozkład prawdopodobieństwa, to mówimy, że cel nie ma wpływu. Jeśli jesteś zainteresowany, model, nad którym pracowaliśmy, nazywa się modelem VIQ, który moim zdaniem jest najbardziej interesującym modelem uczenia się obwodu. Został zdefiniowany w ( cs.yale.edu/homes/aspnes/… ) przez Angluin i in. w STOC '06.
Lew Reyzin