Pytania otagowane jako big-list

Pytania, których odpowiedzi to duża lista pozycji (książki, twierdzenia, oprogramowanie, ...)

5
Nieformalne wycieczki po dowodach
Dzisiaj Ryan Williams opublikował artykuł na temat arXiv (wcześniej ukazał się w SIGACT News) zawierający mniej techniczną wersję swojej najnowszej techniki ACC z dolną granicą. Moje pytanie nie dotyczy samej techniki (oczywiście godnej wielkiej pochwały), ale dotyczy stylu pracy. W streszczeniu pisze: Dowód zostanie opisany z perspektywy osoby próbującej go …
10
Zastosowania złożoności Kołmogorowa w złożoności obliczeniowej
Nieformalnie mówiąc, złożoność Kołmogorowa ciągu jest długością najkrótszego programu, który wypisuje . Możemy zdefiniować pojęcie „losowego ciągu” używając go ( jest losowy, jeśli ) Łatwo jest zauważyć, że większość ciągów jest losowa (nie ma tak wielu krótkich programów).x x K ( x ) ≥ 0,99 | x |xxxxxxxxxK.( x ) …
22
Jakie znasz hierarchie i / lub twierdzenia dotyczące hierarchii?
Obecnie piszę ankietę na temat twierdzeń hierarchicznych dotyczących TCS. Szukając powiązanych artykułów zauważyłem, że hierarchia jest fundamentalną koncepcją nie tylko w TCS i matematyce, ale w wielu naukach, od teologii i socjologii po biologię i chemię. Widząc, że ilość informacji jest ogromna, mam nadzieję, że mógłbym poprosić o pomoc tę …
8
Rygor prowadzący do wglądu
Na MathOverflow Timothy Gowers zadał pytanie zatytułowane „ Wykazanie, że rygor jest ważny ”. Większość dyskusji dotyczyła przypadków pokazujących wagę dowodu, o których ludzie w CSTheory prawdopodobnie nie muszą być przekonani. Z mojego doświadczenia wynika, że ​​dowody muszą być bardziej rygorystyczne w informatyce teoretycznej niż w wielu częściach ciągłej matematyki, …
13
Teoretycznie stosowanie kodów korygujących błędy
Jakie są zastosowania kodów korekcji błędów w teorii oprócz samej korekcji błędów? Jestem świadomy trzech zastosowań: twierdzenia Goldreicha-Levina o twardym rdzeniu, konstrukcji ekstraktora Trevisana i wzmocnienia twardości funkcji boolowskiej (autor: Sudan-Trevisan-Vadhan). Jakie są inne „poważne” lub „rekreacyjne” zastosowania kodów korygujących błędy? UPD: jedna zabawna aplikacja do dekodowania list kodów Reeda-Solomona …
1
Warunek do nauki GCT
Wydaje się, że Teoria Złożoności Geometrycznej wymaga dużej wiedzy na temat czystej matematyki, takiej jak geometria algebraiczna, teoria reprezentacji. Chociaż jestem studentem CS i NIE mam zajęć z bardzo abstrakcyjnej i czystej matematyki, interesuje mnie ten program. Czy istnieje lista „minimalnej wiedzy” do nauki tej teorii? Ta lista zawiera notatki …
17
Przypuszczenia sugerujące twierdzenie o czterech kolorach
Twierdzenie o czterech kolorach (4CT) stwierdza, że ​​każdy płaski wykres jest czterokolorowy. Istnieją dwa dowody podane przez [Appel, Haken 1976] i [Robertson, Sanders, Seymour, Thomas 1997]. Oba te dowody są wspierane komputerowo i dość przerażające. Istnieje kilka domysłów w teorii grafów, które sugerują 4CT. Rozwiązanie tych przypuszczeń wymaga prawdopodobnie lepszego …
2
Trudne problemy z sumą pierwiastków kwadratowych?
Suma pierwiastki problemu prosi, ponieważ dwie sekwencje i dodatnich liczb całkowitych czy suma mniejszy, równy lub większy niż suma . Status złożoności tego problemu jest otwarty; zobacz ten post, aby uzyskać więcej informacji. Problem ten powstaje naturalnie w geometrii obliczeniowej, szczególnie w problemach związanych z najkrótszymi ścieżkami euklidesowymi, i stanowi …
13
Łatwy problem decyzyjny, trudny problem wyszukiwania
Decyzja, czy istnieje równowaga Nasha, jest łatwa (zawsze tak jest); jednak znalezienie takiego uważa się za trudne (jest to PPAD-Complete). Jakie są inne przykłady problemów, w których wersja decyzyjna jest łatwa, ale wersja wyszukiwania jest stosunkowo trudna (w porównaniu z wersją decyzyjną)? Byłbym szczególnie zainteresowany problemami, w których wersja decyzyjna …
4
Dowody, które ujawniają głębszą strukturę
Standardowy dowód na powiązanie z Chernoffem (z podręcznika Randomized Algorytmy ) korzysta z funkcji nierówności Markowa i funkcji generowania momentu, z odrobiną rozszerzenia Taylora. Nic zbyt trudnego, ale nieco mechanicznego. Ale istnieją inne dowody związane z Chernoffem, które ujawniają głębszą strukturę napędzającą wynik. Na przykład istnieje wersja teoretyczno-informacyjna, która wykorzystuje …
35 big-list  proofs 
14
Codzienne problemy z NP-zupełnymi problemami
Mark Dominus zebrał kilka przykładów redukcji czasu wielomianowego od różnych trudnych problemów NP do dopasowania „wyrażenia regularnego” . Wyobrażanie sobie weryfikacji w czasie wielomianowym nie jest ogromnym skokiem. Jak zilustrujesz klasę NP-zupełną studentom lub przyjaciołom z innych dziedzin, którzy chcieli zrozumieć niedawne zamieszanie związane z pracą Deolalikara?
3
Założenia antologii złożoności
W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń, albo hipotezy losowej wyroczni. Najważniejszym i powszechnie uznawanym założeniem jest to, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.