Pytania otagowane jako big-picture

Znacznik dużego obrazu służy do „szerokiego, ogólnego widoku lub perspektywy problemu lub problemu”.

1
Jak mogę wykorzystać moją teorię obliczeniową i moce analizy dla większego dobra?
Jakie są zastosowania moich „mocy” poza środowiskiem akademickim? Co mogę zrobić poza nauczaniem i publikowaniem artykułów? Gdzie wszystko mogę zastosować swoje uprawnienia? Dla argumentu: proszę założyć, że mam doktorat z algorytmów / TCS i nauczyłem się wielu „rzeczy” i stworzyłem przełomowe granice istniejących algorytmów itp., A także mam solidne podstawy …
3
AM / MA i NP analogicznie do P i BPP
Arora i Barak pokazują, że można wyrazić jako B P ⋅ N P, tj. Zestaw języków, w których losowe obniżki do 3SAT. M jest także naturalnym randomizowane uogólnienie N P w które zastąpi deterministyczny weryfikatora przez randomizowanym jeden.AMAM\mathsf{AM}BP⋅NPBP⋅NP\mathsf{BP}\cdot \mathsf{NP}MAMA\mathsf{MA}NPNP\mathsf{NP} Czy istnieje sens, w którym jedno z nich jest ściślej dopasowane …
4
Jakie jest najważniejsze pojęcie rzadkości w projektowaniu wydajnych algorytmów graficznych?
Istnieje kilka konkurencyjnych pojęć „rzadkiego wykresu”. Na przykład wykres, który można osadzić na powierzchni, można uznać za rzadki. Lub wykres z ograniczoną gęstością krawędzi. Lub wykres z wysokim obwodem. Wykres z dużym rozszerzeniem. Wykres z ograniczoną szerokością. (Nawet w obrębie podpól losowych wykresów jest nieco niejednoznaczne co do tego, co …
2
Najlepszy protokół komunikacyjny dla obcych?
Załóżmy, że odkrywamy obce cywilizacje, które są w stanie wysyłać i odbierać wiadomości za pomocą międzygwiezdnego kanału komunikacji cyfrowej. (Powiedz, używając modulowanych fal radiowych, impulsów laserowych, zmiany położenia gwiazd na różnych orbitach, co masz). Załóżmy, że postanowiliśmy się z nimi skontaktować. Po zainicjowaniu dialogu, jak byśmy przystąpili do ustanowienia protokołu …
2
Konsekwencja PIT w stosunku do bez wydajnego algorytmu
Biorąc pod uwagę tak, że współczynniki są ograniczone przez , czy trzymać?p , q B p ≡ qp(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.Z⊂QZ⊂Q\Bbb Z\subset\Bbb Q Oczekujemy, że ten problem będzie miał skuteczną derandomizację. Jakie …
2
Czy istnieje wytłumaczenie trudności w udowodnieniu kwadratowych dolnych granic dla interesujących problemów NP?
To kontynuacja mojego poprzedniego pytania: Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP Uważam za zdumiewające, że nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu w dolnej granicy jakiegokolwiek interesującego problemu NP, na który ludzie dbają i starają się zaprojektować lepsze algorytmy. Nasza hipoteza o wykładniczym …
4
Ludzka inteligencja i algorytmy
Czy były jakieś badania mające na celu ustalenie, czy ludzka inteligencja może przewyższyć algorytmy (tj. Sprawdzenie, czy twierdzenie o braku wolnego obiadu ma zastosowanie do ludzkiej inteligencji)? W tym samym sensie, czy ktoś opracował metodę techniczną, aby wykorzystać dowolne unikalne, ponadkomputerowe właściwości ludzkiej inteligencji?
7
Jak informatyka teoretyczna odnosi się do bezpieczeństwa?
Kiedy myślę o oprogramowaniu, które nie jest bezpieczne, myślę, że jest ono „zbyt przydatne” i może zostać wykorzystane przez napastnika. W pewnym sensie zabezpieczenie oprogramowania to proces zmniejszania jego użyteczności. W informatyce teoretycznej nie pracujesz w prawdziwym świecie. Czy są jakieś obawy związane z bezpieczeństwem podczas pracy z czystą teorią? …
3
Czy istnieje teoria odpowiadająca na „najprostszy program do rozwiązania problemu”?
Aby odpowiedzieć „jakie problemy można rozwiązać za pomocą komputera”, opracowaliśmy teorię obliczalności. Czy w przypadku problemów, które można obliczać, istnieje teoria, która pozwala odpowiedzieć na pytanie „czy program otrzymuję najprostszy”? Nie sądzę, aby złożoność obliczeniowa odpowiadała na pytanie. Myślę, że bierze pod uwagę, jak długo potrzebujemy (choć mierzone abstrakcyjnie). Nie …
2
Co się stanie, jeśli poprawimy twierdzenia dotyczące hierarchii czasu?
f,gf,gf,gf(n)logf(n)=o(g(n))f(n)log⁡f(n)=o(g(n))f(n) \log f(n) = o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )DTIME(f(n))⊊DTIME(g(n))DTIME(f(n))⊊DTIME(g(n)) DTIME(f(n)) \subsetneq DTIME(g(n))f,gf,gf,gf(n+1)=o(g(n))f(n+1)=o(g(n))f(n+1)=o(g(n))jest to NTIME(f(n))⊊NTIME(g(n)).NTIME(f(n))⊊NTIME(g(n)). NTIME(f(n)) \subsetneq NTIME(g(n)). Istnieje wiele (starych i aktualnych) wyników, które wykorzystują twierdzenia o hierarchii czasu do udowodnienia dolnych granic. Oto moje pytania: Co się …
3
Dlaczego nie używamy większych klas do badania determinizmu kontra niedeterminizmu?
W poprzednim pytaniu dotyczącym hierarchii czasu dowiedziałem się, że równości między dwiema klasami mogą być propagowane do bardziej złożonych klas, a nierówności mogą być propagowane do mniej złożonych klas, z argumentami wykorzystującymi wypełnianie. Dlatego przychodzi mi na myśl pytanie. Dlaczego badamy pytanie dotyczące różnych rodzajów obliczeń (lub zasobów) w najmniejszej …
1
Na jakie „pytanie” stara się odpowiedzieć teoria języka programowania?
Od jakiegoś czasu interesowałem się różnymi tematami, takimi jak logika kombinacyjna, rachunek lambda, programowanie funkcjonalne i studiowałem je. Jednak w przeciwieństwie do „teorii obliczeń”, która stara się odpowiedzieć na pytanie „obliczalności”, tj. Rzeczy, które można / nie można obliczyć z różnymi ograniczeniami, staram się znaleźć analogię do „teorii programowania” Wikipedia …
2
Jak / dlaczego systemy liniowe są tak ważne dla informatyki?
Zainteresowałem się optymalizacją matematyczną całkiem niedawno i bardzo mi się podoba. Wydaje się, że wiele problemów związanych z optymalizacją można łatwo wyrazić i rozwiązać jako programy liniowe (np. Przepływy sieciowe, pokrycie krawędzi / wierzchołków, podróżujący sprzedawca itp.) Wiem, że niektóre z nich są trudne do NP, ale chodzi o 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.