Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Zasada Minimax Yao dotycząca algorytmów Monte Carlo
Słynny Yao Minimax Zasada stwierdza zależność między złożonością i dystrybucyjnej randomizowanym złożoności. Niech PPP być problemu ze skończonego zbioru wejść i skończonego zbioru deterministycznego algorytmu rozwiązania . Niech także oznacza rozkład wejściowy, a niech oznacza rozkład prawdopodobieństwa na . Następnie zasada głosi: XX\mathcal{X}AA\mathcal{A}PPPDD\mathcal{D}RR\mathcal{R}AA\mathcal{A}minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and …
3
Dodawanie liczb całkowitych reprezentowanych przez ich faktoryzację jest tak trudne, jak faktoring? Wniosek o referencję
Szukam odwołania do następującego wyniku: Dodanie dwóch liczb całkowitych do reprezentacji faktoryzowanej jest tak trudne, jak dodanie dwóch liczb całkowitych do zwykłej reprezentacji binarnej. (Jestem prawie pewien, że tam jest, ponieważ zastanawiałem się nad tym, a potem byłem podekscytowany, gdy w końcu zobaczyłem to w druku). Problemem jest „dodanie dwóch …
2
Zależność między trudnością rozpoznawania klasy grafowej a zakazaną charakterystyką subgrafu
Rozważam klasy grafów, które można scharakteryzować za pomocą zabronionych subgrafów. Jeśli klasa grafów ma skończony zestaw zabronionych podgraphów, wówczas istnieje trywialny algorytm wielomianowego rozpoznawania czasu (można po prostu użyć brutalnej siły). Ale nieskończona rodzina zakazanych subgraphów nie oznacza twardości: istnieją pewne klasy z nieskończoną listą zakazanych subgrafów, tak że rozpoznanie …
5
Aplikacje Vertex Cover w prawdziwym świecie
Jakie aplikacje mają problemy z wierzchołkiem w prawdziwym świecie? Które projekty branżowe lub badawcze wykorzystują faktycznie zaimplementowane oprogramowanie oparte na teoretycznych wynikach problemu dotyczącego Vertex Cover? W szczególności, czy któryś z poniższych wyników teoretycznych jest wdrażany w używanym oprogramowaniu? Algorytmy aproksymacyjne dla pokrywy wierzchołków Algorytmy czasu wykładniczego dla osłony wierzchołków …
1
Czy twardość NP oznacza twardość P?
Jeśli problem jest trudny dla NP (przy użyciu wielomianowych redukcji czasu), czy to oznacza, że ​​jest trudny dla P (przy użyciu przestrzeni dziennika lub redukcji NC)? Wydaje się intuicyjne, że jeśli jest tak trudny jak jakikolwiek problem w NP, powinien być tak trudny jak jakikolwiek problem w P, ale nie …
1
Maksymalny przepływ dzięki Ford-Fulkerson i DFS
To pytanie dotyczy złożoności czasowej algorytmu maksymalnego przepływu Forda-Fulkersona podczas korzystania z DFS w celu znalezienia ścieżek rozszerzających. Istnieje dobrze znany przykład pokazujący, że przy użyciu DFS można potrzebować liniowej liczby iteracji w maksymalnym przepływie, patrz na przykład strona Wikipedii, do której prowadzi link powyżej. Jednak tak naprawdę nie przekonuje …
1
Dzielony stos
Co wiadomo na temat struktur danych, które mogą utrzymywać sekwencję elementów podlegających następującym dwóm operacjom? Naciśnij (x): dodaj x na końcu sekwencji i zwróć identyfikator jej pozycji w sekwencji Wyodrębnij (S): biorąc pod uwagę nieuporządkowany zestaw identyfikatorów, usuń elementy z tych pozycji z sekwencji i zwróć listę usuniętych elementów w …
2
Numer podziału protokołu i deterministyczna złożoność komunikacji
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997) daje cc(R)/3≤log2(pp(R))≤cc(R).cc(R)/3≤log2⁡(pp(R))≤cc(R).cc(R)/3 \le \log_2(pp(R)) \le cc(R). Jeśli chodzi o drugą nierówność, łatwo jest podać …
3
Źródło edukacyjne lub ankieta na temat analizy programu półfinałowego?
Podczas projektowania algorytmów aproksymacyjnych czasami rozwiązuje się program półfinałowy, po którym następuje etap zaokrąglania. Często ilustrowanym przykładem jest Max-Cut. (Zobacz np. Algorytmy aproksymacji Vijay Vazirani.) Czy istnieją dobre źródła edukacyjne lub ankiety wykraczające poza problem Max-Cut w celu wyjaśnienia bardziej złożonych algorytmów zaokrąglania i technik wykorzystywanych do ich analizy? Mam …
5
Problem z obliczalnością nauczania
Mam trudności z nauczeniem pojęcia funkcji obliczalnych. Próbowałem rozwinąć pojęcie, dlaczego badacze tacy jak Hilbert / Ackermann / Godel / Turing / Church / ... wymyślili pojęcie „obliczalności”. Uczniowie natychmiast zapytali: „co oznacza obliczalność?” i nie mogę odpowiedzieć, dopóki nie nauczę ich maszyn Turinga, a następnie odpowiem „funkcja jest obliczalna, …
1
Złożoność obliczania najkrótszych ścieżek w płaszczyźnie z wielokątnymi przeszkodami
Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że współrzędne s i t oraz współrzędne każdego wierzchołka …
1
W jaki sposób papier BosonSampling unika łatwych klas złożonych matryc?
W złożoności obliczeniowej optyki liniowej ( ECCC TR10-170 ) Scott Aaronson i Alex Arkhipov twierdzą, że jeśli komputery kwantowe mogą być skutecznie symulowane przez klasyczne komputery, hierarchia wielomianowa upadnie na trzeci poziom. Problemem motywującym jest próbkowanie z rozkładu określonego przez sieć liniowo-optyczną; rozkład ten można wyrazić jako stały dla określonej …
1
Zagadnienia energetyczne dotyczące obliczeń
Aby sprawdzić moje zrozumienie, chciałbym podzielić się przemyśleniami na temat wymagań energetycznych obliczeń. Jest to kontynuacja mojego poprzedniego pytania i może być związana z pytaniem Vinaya dotyczącym praw ochrony . Przyszło mi do głowy, że z termodynamicznego punktu widzenia prowadzenie obliczeń można w pewnym stopniu uznać za analogiczne do przemieszczania …
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.