Najbardziej wpływowe wyniki Liptona

Richard J. Lipton został wybrany zwycięzcą nagrody Knuth Prize 2014 „za wprowadzenie nowych pomysłów i technik”.

Jakie są według Ciebie główne nowe pomysły i techniki opracowane przez Lipton?

Uwaga. To pytanie stanie się wiki społeczności, proszę podać jeden taki pomysł, technikę lub wynik na odpowiedź.

Planarny Separator twierdzenie wskazuje, że w każdej płaskiej -Vertex wykres G istnieje zestaw O ( $n$$G$wierzchołki, których usunięcie pozostawia wykres odłączony na co najmniej dwa zgrubnie zrównoważone elementy. Co więcej, taki zestaw można znaleźć w czasie liniowym. Ten (ścisły) wynik,udowodniony przez Liptona i Tarjana(poprawiający poprzedni wynik przez Ungara) jest potężnym narzędziem do projektowania algorytmów na wykresach płaskich. Daje wiele dokładnych algorytmów podwykładniczych dla problemów trudnych dla NP i ulepszone algorytmy aproksymacji czasu wielomianowego. Spojrzenie nastronę wikipediidaje dobre miejsce do rozpoczęcia odkrywania licznych aplikacji. Wcześnie Badaniez podaniem liczby wniosków został napisany przez Lipton i Tarjan w 1980 roku.$O(\sqrt{n})$

Karp-Lipton Twierdzenie mówi, że nie może mieć wielomian-size obwodów logicznych, chyba że Wielomian hierarchia zapada na drugim poziomie.$\mathsf{NP}$

Dwa implikacje tego twierdzenia dla teorii złożoności:

• prawdopodobnie nie ma obwodów boolowskich o wielkości wielomianowej; udowodnienie niższych granic wielkości obwodów jest zatem możliwym podejściem do rozdzielania klas złożoności.$\mathsf{NP}$
• Kilka wyników opiera się na tym twierdzeniu, aby udowodnić rozdzielenie klas złożoności (na przykład Twierdzenie Kannana).

Losowa samoodwracalność permanentna . Lipton wykazał, że jeśli istnieje algorytm, który poprawnie oblicza stały ułamek wszystkich F n × n , gdzie F jest skończonym polem wielkości co najmniej 3 n , to algorytm ten można zastosować jako czarna skrzynka do obliczenia stałej dowolnej macierzy z dużym prawdopodobieństwem.$1-1/(3n)$$\mathbb{F}^{n\times n}$$\mathbb{F}$$3n$

Główną ideą jest to, że permanent jest wielomianem niskiego stopnia, więc jego skład z jednoczynnikową funkcją afiniczną jest wielomianem niskiego stopnia wielomianu (w x ) i można się go nauczyć z niewielkiej liczby wartości poprzez interpolację . Możesz wybrać losowy B, aby kompozycja była rozłożona jako stała losowej macierzy dla dowolnego x . Przy x = 0 jednowymiarowa wielomian jest tylko stały z A . Szczegóły można znaleźć w rozdziale 8 Arory Barak .$A + xB$$x$$B$$x$$x = 0$$A$

To podejście algebraiczne wywarło ogromny wpływ w teorii złożoności. Pomysły Liptona doprowadziły ostatecznie do udowodnienia twierdzenia IP = PSPACE, dowodu twierdzenia PCP oraz do wyników na lokalnych kodach korygujących błędy.

Nie jestem w 100% pewien, czy poniższe wyjaśnienie jest historycznie dokładne. Jeśli tak nie jest, prosimy o edycję lub usunięcie.

Testy mutacyjne zostały wynalezione przez Lipton. Testowanie mutacji może być postrzegane jako sposób pomiaru jakości lub skuteczności zestawu testów. Kluczową ideą jest wstrzyknięcie błędów do testowanego programu (tj. Zmutowanie programu), najlepiej rodzajów błędów, które może popełnić ludzki programista, i sprawdzenie, czy zestaw testów znajdzie wprowadzone błędy. Typowym przykładem tego rodzaju testu mutacji uszkodzeń może być zastąpienie x> 0 x x 0 lub x przez x + 1 lub x-1. Część błędów wykrytych przez zestaw testowy to „wynik adekwatności mutacji” zestawu testowego. Mówiąc bardzo swobodnie, można myśleć o tym jako o metodzie Monte-Carlo do obliczania wyniku adekwatności mutacji.

Mówiąc bardziej abstrakcyjnie, można powiedzieć, że testowanie mutacji wysuwa na pierwszy plan symetrię lub dwoistość między programem a zestawami testów: nie tylko zestaw testów może być użyty do uzyskania większej pewności co do poprawności programu, ale odwrotnie, program może być używane, aby zyskać pewność co do jakości zestawu testów.

W świetle tej dualności testowanie mutacji jest również koncepcyjnie bliskie wstrzyknięciu winy . Oba są technicznie podobne, ale mają różne cele. Testowanie mutacji ma na celu pomiar jakości zestawu testów, podczas gdy wstrzykiwanie błędów ma na celu ustalenie jakości programu, zwykle jakości obsługi błędów.

Ostatnio pomysły z testów mutacji zostały wykorzystane do przetestowania (sformalizowania) teorii logicznych. Parafrazując streszczenie (4): Przy opracowywaniu nietrywialnych formalizacji w dowodzie twierdzącym, znaczną ilość czasu poświęca się na „debugowanie” specyfikacji i twierdzeń. Zazwyczaj nieprawidłowe próby lub twierdzenia są wykrywane podczas nieudanych prób dowodu. Jest to droga forma debugowania. Dlatego często przydaje się testowanie przypuszczeń przed rozpoczęciem dowodu. Możliwym sposobem na to jest przypisanie losowych wartości do wolnych zmiennych hipotezy, a następnie ich ocena. (4) wykorzystuje mutacje do testowania jakości używanych generatorów przypadków testowych.

Historia . Z (1): Historię testów mutacyjnych można prześledzić do 1971 r. W pracy studenckiej Richarda Liptona [...] Narodziny tej dziedziny można również zidentyfikować w innych artykułach opublikowanych pod koniec lat 70. XX w. Przez Liptona i in. (2) oraz Hamleta (3).

1. Repozytorium testów mutacji: teoria testów mutacji .

2. RA DeMillo, RJ Lipton, FG Sayward, Wskazówki dotyczące wyboru danych testowych: Pomoc dla ćwiczącego programisty .

3. RG Hamlet, Testowanie programów z pomocą kompilatora .

4. S. Berghofer, T. Nipkow, Losowe testy w Isabelle / HOL. .

Schwartz - Zippel - DeMillo-Lipton Lemma jest podstawowym narzędziem w złożoności arytmetycznej: Zasadniczo stwierdza, że ​​jeśli chcesz wiedzieć, czy obwód arytmetyczny reprezentuje zerowy wielomian, wystarczy ocenić obwód na jednym wejściu. Wtedy otrzymasz niezerową wartość z dużym prawdopodobieństwem, jeśli obwód nie reprezentuje zerowego wielomianu.

Jest to szczególnie ważny lemat, ponieważ dla tego problemu nie jest znany algorytm deterministyczny czasu wielomianowego.

Lemat jest zwykle znany jako Schwartz-Zippel Lemma . Historię tego lematu można znaleźć na własnym blogu Liptona .

Pokrywalność w systemach dodawania wektorów jest trudna w EXPSPACE : u RJ Liptona Problem osiągalności wymaga przestrzeni wykładniczej , raport z badań 63, Yale University, 1976.

$d$$\langle v_0,A\rangle$$v_0$$\mathbb{N}^d$$A$$\mathbb{Z}^d$$\mathbb{N}^d$$v\to v'$$u$$A$$v'=v+u$$v'$$v$$\mathbb{N}^d$$v_0\to v_1\to\cdots\to v_n$$v_n\geq v$$\mathbb{N}^d$$v_n(i)\geq v(i)$$1\leq i\leq d$. W połączeniu z górną granicą EXPSPACE udowodnioną przez C. Rackoffa w 1978 roku , wynik Liptona pokazuje kompletność EXPSPACE.

$v_n=v$

Złożoność komunikacji wielopartyjnej i model numer na czole zostały wprowadzone przez Ashoka K. Chandrę , Merrick L. Furst i Richarda J. Liptona w protokołach wielopartyjnych , STOC 1983, doi: 10.1145 / 800061.808737 .

Model wielopartyjny jest naturalnym rozszerzeniem dwupartyjnego modelu złożoności komunikacyjnej Yao , w którym Alice i Bob mają nie nakładające się połówki bitów wejściowych i chcą się komunikować, aby obliczyć z góry określoną funkcję całego wejścia. Jednak rozszerzenie partycji bitów wejściowych na większą liczbę stron często nie jest zbyt interesujące (w dolnych granicach zwykle można po prostu wziąć pod uwagę dwie pierwsze strony).

$k$$k$$n$

$n$

$N$$k$$N$$k=3$$N$$O(\sqrt{\log N})$$N \le k(2^n-1)$$O(\sqrt{n})$

$^0$

$N$