Przykłady ceny abstrakcji?

Informatyka teoretyczna dostarczyła kilka przykładów „ceny abstrakcji”. Dwa najbardziej znaczące dotyczą eliminacji i sortowania Gaussa. Mianowicie:

• Wiadomo, że eliminacja Gaussa jest optymalna do, powiedzmy, obliczenia wyznacznika, jeśli ograniczysz operacje do wierszy i kolumn jako całości [1]. Oczywiście algorytm Strassena nie przestrzega tego ograniczenia i jest asymptotycznie lepszy niż eliminacja Gaussa.
• Przy sortowaniu, jeśli traktujesz elementy listy jako czarne skrzynki, które można tylko porównywać i przenosić, mamy standardową dolną granicę teoretyczną informacji teoretycznych. Jednak drzewa syntezy jądrowej pokonały to, o ile rozumiem, sprytne wykorzystanie rozmnażania.$n \log n$

Czy istnieją inne przykłady ceny abstrakcji?

Aby być bardziej formalnym, szukam przykładów, w których dolna granica jest bezwarunkowo znana w słabym modelu obliczeniowym, ale wiadomo, że została naruszona w silniejszym modelu. Ponadto słabość słabego modelu powinna przybierać formę abstrakcji , co wprawdzie jest pojęciem subiektywnym. Na przykład nie uważam ograniczenia obwodów monotonicznych za abstrakcję. Mam nadzieję, że dwa powyższe przykłady wyjaśniają, czego szukam.

[1] KLYUYEV, VV i NI KOKOVKIN-SHcHERBAK: W sprawie minimalizacji liczby operacji arytmetycznych dla rozwiązania liniowych układów algebraicznych równań. Tłumaczenie GI TEE: Raport techniczny CS 24, czerwiec t4, t965, Wydział Informatyki, Uniwersytet Stanforda.

Kolejny piękny przykład ceny abstrakcji: kodowanie sieciowe . Wiadomo, że w ustawieniach multiemisji relacja maksymalnego przepływu i minimalnego cięcia nie jest równa (pierwotna i podwójna nie pasują). Jednak tradycyjne modele zakładają przepływ, który jest po prostu przekazywany i nie „przetwarzany” w żaden sposób. Dzięki kodowaniu sieci możesz przekroczyć ten limit, sprytnie łącząc przepływy. Ten przykład był przede wszystkim świetną motywacją do badań nad kodowaniem sieci.

Czysto funkcjonalne programowanie jest popularną abstrakcją, która oferuje, przynajmniej zdaniem jej zwolenników, ogromny wzrost ekspresyjnej mocy kodu i inne korzyści. Ponieważ jednak jest to model ograniczający maszynę - w szczególności nie zezwalający na zmienną pamięć - rodzi się pytanie o asymptotyczne spowolnienie w porównaniu ze zwykłym modelem (RAM).

Jest to świetny wątek na ten temat tutaj . Najważniejsze rzeczy wydają się:

1. Można symulować pamięć zmienną za pomocą zrównoważonego drzewa binarnego, więc najgorszym spowolnieniem jest O (log n).
2. Z chętną oceną istnieją problemy, dla których jest to najlepsze, co możesz zrobić.
3. W przypadku leniwej oceny nie wiadomo, czy istnieje luka. Istnieje jednak wiele naturalnych problemów, dla których żaden znany czysto funkcjonalny algorytm nie odpowiada optymalnej złożoności pamięci RAM.

Wydaje mi się, że jest to zaskakująco podstawowe pytanie, aby być otwartym.

Podczas gdy twoje pytanie koncentruje się na teorii złożoności, podobne rzeczy mogą się zdarzyć w innych dziedzinach, takich jak teoria języków programowania. Oto kilka przykładów, w których abstrakcja sprawia, że ​​coś jest nierozstrzygalne (tj. Dolna granica w słabym modelu jest niemożliwa, a silny model pozwala na wyrażenie algorytmu):

• W rachunku lambda istnieją funkcje, których nie można wyrazić bezpośrednio (tj. Jako termin lambda, który beta redukuje do pożądanego wyniku). Przykład jest równoległy lub (funkcja dwóch argumentów zwracających ten, który się kończy). Innym przykładem jest funkcja, która wypisuje swój argument dosłownie (funkcja oczywiście nie może rozróżnić dwóch argumentów równoważnych wersji beta). Brak wyrazistości wynika z wymuszenia abstrakcji, że terminy lambda równoważne beta muszą być traktowane identycznie.

• W języku o typie statycznym, który ma tylko polimorfizm parametryczny , takim jak ML bez fantazyjnego rozszerzenia, nie można napisać niektórych funkcji - otrzymujesz twierdzenia za darmo . Na przykład funkcja typu (niezależnie od typu argumentu, zwraca obiekt tego samego typu) musi być funkcją tożsamości lub nie być zakończona. Brak wyrazistości wynika z abstrakcji, że jeśli nie znasz rodzaju wartości, jest ona nieprzezroczysta (możesz ją tylko przekazywać).$\forall\alpha, \alpha\to\alpha$

$\Omega(\sqrt{m})$$m$$\mathbb{Z}_n^*$

$\mathbb{Z}_n^*$

$s$$t$$s$$t$$s$$t$$\min$$+$$\max$$\min$

Niech będzie liczbą wierzchołków na wykresie wejściowym. Wiadomo, że ten problem wymaga czasu w modelu porównywania ścieżek Karger, Koller i Phillips , podobnie jak problem najkrótszych ścieżek wszystkich par. (Model ścieżka porównywania umożliwia tradycyjne algorytmy, takie jak Floyd- Warshall). Jednakże, w przeciwieństwie do wszystkich parach najkrótszej ścieżki, to okazuje się, że wszystkie par wąskie gardło ścieżki mogą być rozwiązane w mniej niż raz stosując szybkie mnożenie macierzy.$n$$\Omega(n^3)$$O(n^{2.8})$

W dyskusji na temat tego pytania wiele problemów w geometrii obliczeniowej ma dolne granice w algebraicznym drzewie decyzyjnym lub modelach obliczeniowych algebraicznego drzewa obliczeniowego, wynikające z podstawowych problemów, takich jak sortowanie lub odróżnianie elementów . Nietrudno znaleźć dokumenty, które twierdzą, że górne granice dotyczące powiązanych problemów, takich jak konstrukcja triangulacji Delaunaya, są optymalne, ponieważ pasują do tych dolnych granic.$\Omega(n\log n)$$O(n\log n)$

Ale gdy dane wejściowe są określone za pomocą liczb całkowitych we współrzędnych kartezjańskich (jak to często bywa w praktyce, ponieważ zmiennoprzecinkowe jest źle dopasowane do geometrii obliczeniowej), te dolne granice nie pasują do modelu obliczeniowego. Być może nie jest zaskakujące, że problemy z wyszukiwaniem zakresu ortogonalnego można rozwiązać szybciej, stosując techniki dostosowane do sortowania liczb całkowitych, ale nawet problemy nieortogonalne często mogą mieć szybsze algorytmy (które dokładnie rozwiązują problem, w modelach obliczeniowych umożliwiających arytmetykę liczb całkowitych z O (1) ) razy dokładność wejściowych liczb całkowitych). Zobacz np. ArXiv: 1010.1948 dla jednego zestawu przykładów.

Istnieje wiele takich przykładów w kryptografii, szczególnie dowody zerowej wiedzy. Zobacz np. Teza:

Boaz Barak, Techniki inne niż czarne skrzynki w kryptografii, 2003.

(Nawiasem mówiąc, tytuł pracy stanowi dowód zerowej wiedzy na temat ważności tego komentarza :)

Algebraiczne drzewa decyzyjne są wykorzystywane jako podstawa w geometrii obliczeniowej, aby pokazać wiele prostych problemów, takich jak Unikalność elementów to . Te dolne granice są następnie wykorzystywane do pokazania bardziej skomplikowanych problemów, takich jak diagramy Voronoi mają również dolne granice . Byłem później zaskoczony, gdy przeczytałem algorytm czasu oczekiwanego do rozwiązania najbliższej pary punktów na płaszczyźnie, który jest uogólnieniem wyjątkowości elementu. Ucieka przed Algebraicznym drzewem decyzyjnym związanym za pomocą haszowania. Znalazłem to w książce „Algorytm projektowania” Kleina i Tardosa. Istnieje podobny, ale bardziej skomplikowany algorytm rozwiązywania tego samego problemu opisanego na blogu RJ Lipton .$\Omega(n \log n)$$\Omega(n \log n)$$O(n)$

Odniesienie:

• Richard J. Lipton, „ Rabin Flips a Coin ”, marzec 2009 r.
  Opublikowany na blogu Godel's Lost Letter i P = NP .

Rozważ synchroniczne deterministyczne algorytmy rozproszone w celu zmniejszenia liczby kolorów na wykresie cyklu z do . Oznacza to, że otrzymujesz właściwe kolorowanie cyklu i chcesz uzyskać prawidłowe kolorowanie cyklu; każdy węzeł cyklu jest procesorem.$k$$3$$k$$3$

Jeśli przyjmiesz model oparty na porównaniu (traktujesz kolorów jako czarne skrzynki, które można przesyłać tylko z jednego węzła do drugiego i porównywać ze sobą), otrzymasz trywialną dolną granicę dla liczby rundy komunikacyjne.$k$$\Omega(k)$

Jednak abstrakcja ta jest ewidentnie błędna: jeśli możesz przesłać coś w sieci komunikacyjnej, będziesz miał sposób na zakodowanie „czegoś” jako ciągu bitów. A teraz wszystko zaczyna wyglądać znacznie lepiej.

Jeśli twoje kolory nie są czarnymi skrzynkami, ale liczbami całkowitymi , możesz wykonać redukcję kolorów za pomocą technik Cole – Vishkin w rundach komunikacji . Nawet jeśli twoje kolory to ogromne ciągi bitów, takie jak liczby całkowite z , otrzymasz to samo związane .$1, 2, ..., k$$O(\log^* k)$$1, 2, ..., 10^{10^k}$$O(\log^* k)$

Konkluzja: cena „niewłaściwej” abstrakcji: vs. .$O(\log^* k)$$\Omega(k)$

Przykładem, który przychodzi mi na myśl, jest obliczanie objętości. W rezultacie Barany i Furedi potrzebują wykładniczej liczby zapytań, a Dyer-Frieze-Kannan stosuje algorytm losowego wielomianu czasu . Luka reprezentuje nagrodę abstrakcji, a także korzyść z losowości, ale myślę, że główną przyczyną luki jest cena abstrakcji. (Mam nadzieję, że zrozumiałem pytanie i idzie w dobrym kierunku).

Prawdopodobnie nie to dokładnie miałeś na myśli. Ale w pewnym sensie niezależność P od NP od wyroczni jest tego przykładem. To, co tak naprawdę mówi, to to, że jeśli wszystko, na czym ci zależy, to symulacja i wyliczanie (tj. Jeśli to jest twój „model” obliczeń), to nie możesz oddzielić tych klas ani ich zwinąć.

Bardziej konkretny przykład algorytmu pochodzi z wyszukiwania przybliżonego zakresu w kierunku „wstecznym”. W szczególności większość problemów z wyszukiwaniem zakresów jest wyrażana jako sumy półgrup, a dolne / górne granice wyrażane są bez względu na strukturę tej półgrupy (z wyjątkiem niektórych lekkich warunków technicznych). Ostatnie prace Aryi, Malamatos i Mount pokazują, że jeśli przyjrzysz się strukturze półgrupy (właściwości idempotencji i integralności), możesz udowodnić różne (i ściślejsze) granice dla wyszukiwania w przybliżeniu zakresu.

Twierdzenie Shannona-Nyquista o próbach proponuje wystarczający warunek dla teoretycznych granic komunikacyjnych w komunikacji. Teoria próbkowania działa na przykładach, w których przychodzący sygnał ma zwartą / losową reprezentację. Ostatnie postępy w próbkowaniu pokazują, że ta abstrakcja może mieć pewną cenę - że rzeczy, które jesteśmy zainteresowani mierzeniem, mają zazwyczaj rzadkie reprezentacje, więc granice te nie są ścisłe. Ponadto informacje mogą być kodowane w znacznie gęstszy sposób niż pierwotnie sądzono.

• Kody korygujące błędy sugerują, że ponowna ocena limitu Shannona w krajobrazach sieciowych narażonych na hałas.
• Zupełnie nowa dziedzina czujników kompresyjnych popycha rekonstrukcję odmian obrazów, które uważamy za interesujące znacznie poza granicami Shannona.

Wiele interesujących problemów, jakie pojawiają się w naukach przyrodniczych, okazuje się trudnych do NP w klasycznym sensie. Chociaż to pojęcie jest teoretycznie całkowicie poprawne, w żaden sposób nie pomaga biologowi ani fizykowi. Stwierdzamy, że niektóre problemy trudne dla NP są parametrami, które można leczyć i często mają parametr, który jest obserwowany jako ograniczony przez małą stałą w świecie rzeczywistym.

Oznacza to, że TCS mówi nam, że nie oczekujemy wydajnego rozwiązania abstrakcyjnego problemu, ale możemy szybko rozwiązać rzeczywiście występujące przypadki - dość duża luka.

W tym artykule http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf badaliśmy maszyny Turinga, które mają ograniczony dostęp do danych. Jest to sformalizowane jako niezmienne przy automorfizmach struktury relacyjnej; na przykład w dolnej granicy sortowania O (n log n) można powiedzieć, że maszyna może przetwarzać i przechowywać liczby wymierne, ale jej przejścia powinny być niezmienne w przypadku automorfizmów (Q, <), tj. biotuzji monotonicznych. Formalna definicja jest bardziej skomplikowana, aby dokładnie określić, jakie struktury danych może przechowywać maszyna w swojej pamięci (
w pewnym sensie powinna być „skończona” , ale pozwalamy na przechowywanie bardziej skomplikowanych struktur niż tylko krotek wartości danych, takie jak nieuporządkowane krotki).

W artykule udowodniliśmy pewne dolne granice dla innych maszyn Turinga z „ograniczonym dostępem do danych”. W szczególności pokazaliśmy, że:

• Deterministyczna maszyna Turinga, która może obsługiwać wektory (powiedzmy nad polem dwuelementowym), ale może korzystać tylko z testów dodawania wektora i równości, nie może określić w czasie wielomianowym, czy dana lista wektorów jest liniowo zależna (formalnie przejścia maszyn powinny być niezmiennym przy automorfizmach przestrzeni wektorowej). Jest to przeciwieństwo niedeterministycznych maszyn, które mogą po prostu zgadywać kombinację wektorów, która daje w sumie 0. Zauważ, że eliminacja Gaussa przebiega w czasie wielomianowym, ale ma dostęp do współrzędnych wektorów; w szczególności jego przejścia nie są niezmienne przy automorfizmach przestrzeni wektorowej.

• W odpowiednio zdefiniowanym modelu nie można określić Maszyn Turinga, które mogą porównywać liczby naturalne tylko w odniesieniu do równości (nawet <). Rozważamy tutaj strukturę relacyjną (N, =) i maszyny, które są niezmienne w ramach jej automorfizmów. Istnieje konstrukcja (podobna do konstrukcji Cai-Furera-Immermana z teorii modeli skończonych), która pokazuje, że w rzeczywistości w tym modelu P ≠ NP. Umożliwienie maszynom porównania liczb za pomocą <daje im wystarczającą moc do ustalenia.

Ogólna cena abstrakcji jest obecna w ramach czarnej skrzynki, takich jak złożoność drzewa decyzyjnego lub złożoność kwantowych zapytań. Jeśli ograniczymy analizę do tych modeli, często możemy znaleźć bardzo dobre granice złożoności zadań. W rzeczywistości dla kwantowego zapytania możemy zasadniczo rozwiązać złożoność problemów, ponieważ metoda negatywnego przeciwnika zapewnia ścisłe dolne granice (w ramach współczynnika log n / loglog n: 1005.1601 ). Daje nam to doskonałe narzędzie do analizy złożoności zapytań, ale często trudno jest porównać złożoność zapytań z bardziej standardową złożonością czasu / przestrzeni maszyny Turinga (z wyjątkiem surowej dolnej granicy).

Oto dwa przykłady, oba związane z modelami ciągłymi i dyskretnymi:

1. Załóżmy, że w przedziale ukryty jest (nieskończenie mały) skarb w pozycji . Chcemy znaleźć skarb, kopiąc. Ilekroć kopiemy w pozycji , otrzymujemy informację zwrotną, czy , lub . Oczywiście, jeśli może być dowolną liczbą rzeczywistą, wówczas dowolny algorytm wyszukiwania może nigdy nie zostać zakończony. mogą być bardzo małe, ale nigdy nie osiągniemy . x y x < y x = y x > y x | x - y | y = $[0,1]$$x$$y$$x<y$$x=y$$x>y$$x$$|x-y|$$y=x$

   Możemy jednak rozszerzyć model wyszukiwania, aby umożliwić ciągłe zamiatanie. W tym modelu po prostu pozwalamy pracować w sposób ciągły w przedziale i otrzymywać informacje zwrotne za każdym razem, gdy .[ 0 , 1 ] y = $y$$[0,1]$$y=x$

2. Motywacja problemu A wynika z problemu podziału ciastek bez zazdrości . Stromquist pokazał , że żaden skończony protokół (nawet jeśli jest nieograniczony) nie może zagwarantować wolnego od zazdrości podziału ciasta na trzech lub więcej graczy, jeśli każdy gracz ma otrzymać jeden połączony kawałek.

   Jednak, jak wyjaśnili Aumann i Dombb , wynik ten dotyczy tylko dyskretnego modelu cięcia, w którym „Na każdym etapie protokół wybiera odtwarzacz oraz liczbę rzeczywistą i zaprasza gracza do zaznaczenia znaku w unikalnym punkcie dla których "," i nie w przypadkach, gdy na przykład jakiś mediator ma pełną informację o funkcjach wyceny graczy i proponuje podział na podstawie tych informacji ". α i x v i ( 0 , x ) = $i$$\alpha$$i$$x$$vi(0,x) = \alpha$

   Ponadto wynik nie dotyczy algorytmów z ciągłymi operacjami, takimi jak procedury z ruchomym nożem.

Wyrażony w logice pierwszego rzędu, każdy dowód zasady szuflady dla ustalonego n ma wykładniczą długość. Jednak w przypadku arytmetyki dowód można wyrazić o wiele bardziej zwięźle.

Sukces solverów SMT wynika z wycofania się z abstrakcyjnego modelu zmniejszania problemów do SAT, pozwalając bogatszym teoriom znacznie zmniejszyć liczbę potrzebnych obliczeń.