Teoretyczne informatyka

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

1
Inne zastosowania wzmocnienia rozgałęzień Karger-Stein?
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która doprowadzi ten punkt do domu.) Algorytm Kargera i Steina jest …
2
Dokumenty do uznania za spektralny podział grafów
Jeśli jest nieukierunkowane -regular wykres i jest podzbiorem wierzchołków liczności , wywołać ekspansję krawędzi o o ilościd S ≤ | V | / 2G=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edge s ( S, V- S)re⋅ | S.| ⋅ | V.- S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|} Gdzie jest liczbą krawędzi z jednego punktu końcowego …
3
Czy istnieje kandydat na naturalny problem w ?
Chcę wiedzieć, czy niejednorodność pomaga w praktyce funkcji obliczeniowych. Łatwo jest pokazać, że istnieją funkcje w , weź dowolną funkcję nieobliczalną i rozważ język { }, który wyraźnie ma proste niejednorodne obwody , ale w ogóle nie da się go obliczyć jednolicie, ale to nie są funkcje, którymi się interesuję.P/poly−PP/poly−PP/poly …
6
Jak określa się liczby rzeczywiste w obliczeniach?
To może być podstawowe pytanie, ale czytałem i próbowałem zrozumieć artykuły na takie tematy, jak obliczenia równowagi Nasha i liniowe testy degeneracji, i nie byłem pewien, jak liczby rzeczywiste są określone jako dane wejściowe. Na przykład, kiedy stwierdzono, że LDT ma pewne dolne granice wielomianu, w jaki sposób określa się …
4
Twierdzenie Kościoła i twierdzenia o niekompletności Gödla
Niedawno czytałem o niektórych pomysłach i historii przełomowej pracy wykonanej przez różnych logików i matematyków w zakresie obliczeń. Podczas gdy poszczególne koncepcje są dla mnie dość jasne, staram się dobrze zrozumieć wzajemne relacje i abstrakcyjny poziom, na którym wszystkie są ze sobą powiązane. Wiemy, że twierdzenie Kościoła (a raczej niezależne …
6
Dobrze znane klasy wzorów boolowskich, które wymagają wykładniczo długich prób rozdzielczości
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania rozdzielczości i używają kombinacji innych rzeczy po prostu do pomocy i do …
2
Jakie są konsekwencje parzystości-L = P?
Parzystość-L jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może jedynie rozróżniać między liczbą parzystą lub nieparzystą liczbą ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji), i która jest dodatkowo ograniczone do pracy w przestrzeni logarytmicznej. Rozwiązanie liniowego układu równań powyżej ℤ 2 jest kompletnym problemem dla parzystości-L, …
4
Algorytmy kwantowej aproksymacji
Ogólnie uważa się za mało prawdopodobne, aby komputery kwantowe były w stanie skutecznie rozwiązywać problemy związane z NP. W klasycznym przypadku jednym podejściem do rozwiązania takich problemów jest zastosowanie algorytmów aproksymacyjnych. Czy były jakieś badania algorytmów aproksymacyjnych wykorzystujących obliczenia kwantowe, w których kwantowość znacznie przyspiesza w porównaniu z klasycznymi metodami …
1
Czy znane są algorytmy podwykładnicze dla PLANAR SAT?
Niektóre problemy trudne NP, które są wykładnicze na grafach ogólnych, są sub wykładnicze na grafach płaskich, ponieważ szerokość wynosi co najwyżej i są wykładnicze w szerokości.4,9 | V.( G ) |------√4.9|V(G)|4.9 \sqrt{|V(G)|} Zasadniczo jestem zainteresowany, czy istnieją algorytmy podwykładnicze dla PLANAR SAT, który jest NP-zupełny. Niech być wzór nanowłókien węglowych …
1
Rabin – Karp vs Karp – Rabin
Mądrzy inni redaktorzy Wikipedii odrzucili moją prośbę o przeniesienie artykułu z Wikipedii na temat algorytmu Rabin – Karp do tego, co moim zdaniem powinno się nazywać, algorytm Karp – Rabin, ponieważ częściej używa się nazwy Rabin – Karp ( fałsz, jeśli ktoś idzie według liczb uczonego Google) lub że brzmi …
1
Czy istnieje zwykły język drzewa, w którym średnia wysokość drzewa o rozmiarze nie jest ani ani ?
Definiujemy zwykły język drzewa, tak jak w książce TATA : Jest to zestaw drzew akceptowany przez niedeterministyczny automat skończonego drzewa (rozdział 1) lub, równoważnie, zbiór drzew wygenerowany przez zwykłą gramatykę drzewa (rozdział 2). Oba formalizmy są bardzo podobne do znanych analogów strunowych. Czy istnieje zwykły język drzewa, w którym średnia …
1
Złożoność zasilania macierzy
Niech będzie kwadratową macierzą liczb całkowitych, a niech n będzie liczbą całkowitą dodatnią. Interesuje mnie złożoność następującego problemu decyzyjnego:MMMnnn Czy prawy górny wpis dodatni?MnMnM^n Zauważ, że oczywiste podejście iterowanego kwadratu (lub innego jawnego obliczenia) wymaga od nas potencjalnie obsługi liczb całkowitych o podwójnie wykładniczej wielkości, tj. Mających wykładniczo wiele bitów. …
6
Czy można powrócić do pracy badawczej TCS po wycieczce do pracy w branży niezwiązanej z badaniami?
Słyszałem od niektórych starszych naukowców zajmujących się informatyką teoretyczną, że praca w branży niezwiązanej z badaniami, nawet przez kilka lat, zabije twoją karierę jako badacz TCS. Jestem jednak podejrzliwy wobec twierdzenia, że ​​droga od bycia badaczem TCS do pracy niezwiązanej z badaniami w branży to droga jednokierunkowa. Chcę wiedzieć, czy …
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.