Teoretyczne informatyka

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

6
Struktura danych dla zbiorów drzew.
Próby pozwalają na efektywne przechowywanie list elementów. Prefiksy są wspólne, więc zajmuje mało miejsca. Szukam podobnego sposobu skutecznego przechowywania drzew. Chciałbym móc sprawdzać członkostwo i dodawać elementy, wiedząc, czy dane drzewo jest poddrzewem niektórych przechowywanych drzew, czy też istnieje drzewo przechowywane, które jest poddrzewem danego drzewa. Zazwyczaj przechowywałem około 500 …
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 …
1
Programy rozpiętości, rozmiar świadka i złożoność certyfikatu
Program zakresu to liniowo-algebraiczny sposób określania wprowadzonej tutaj funkcji boolowskiej . Ostatnio model ten został użyty do wykazania, że ​​metoda negatywnego przeciwnika zapewnia ścisłą charakterystykę (przynajmniej do ) złożoności kwantowych zapytań.logn/loglognlog⁡n/log⁡log⁡n\log n/ \log \log n Miarą złożoności łączącą programy zakresu z kwantową złożonością zapytań jest wielkość świadka. Ta miara wydaje …
2
Istnienie
Rozważ problem z zestawem dominującym na ogólnych wykresach i niech będzie liczbą wierzchołków na wykresie. Chciwy algorytm aproksymacji daje gwarancję aproksymacji współczynnika , tzn. Możliwe jest znalezienie w czasie wielomianowym rozwiązania takiego, że , gdzie jest rozmiarem minimalnego zestawu dominującego. Istnieją ograniczenia wskazujące, że nie możemy poprawić zależności od dużo …
1
Funkcja Lovasz theta i wykresy regularne (w szczególności cykle nieparzyste) - związki z teorią spektralną
Wpis dotyczy: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Jak dalece Lovasz jest związany ze zdolnością do zerowego błędu regularnych grafów? Czy istnieją przykłady, w których wiadomo, że ograniczenie Lovasz nie jest równe pojemności zerowego błędu zwykłego wykresu? (Oleksandr Bondarenko odpowiedział poniżej). W szczególności czy znana jest jakakolwiek ścisła nierówność dla nieparzystych cykli boków większych lub …
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ę …
4
Konstrukcje lepsze niż losowe.
Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe. Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe. Można łatwo skonstruować takie sztuczne przykłady. Interesują mnie przykłady takie jak algebraiczne kody geometrii, w których …
1
Problem dotyczący minimalnego pokrycia ścieżki
Pracujemy na rozproszonych komputerach i znaleźliśmy problem złożoności, który sprowadza się do minimalnego problemu obejmującego ścieżkę. Obecnie nie wiemy, jak to rozwiązać. Problem jest następujący: Niech będzie liczbą całkowitą, a będzie wykresem zawierającym wierzchołki . Każdy wierzchołek oznaczamy parą taką, że . Odtąd nazywamy wierzchołki za pomocą ich etykiety. Zestaw …
4
Jakie są główne trudności w przechodzeniu od wykresów do hipergraphów?
W kombinatoryce i informatyce istnieje wiele przykładów, w których możemy analizować problem teoretyczny na wykresach, ale w przypadku analogu hipergrraficznego problemu brakuje naszych narzędzi. Jak myślisz, dlaczego problemy często stają się znacznie trudniejsze w przypadku 3-jednolitych hiperrafów niż w przypadku 2-jednolitych wykresów? Jakie są podstawowe trudności? Jedną kwestią jest to, …
3
Zastosowania MCTS / UCT
MCTS / UCT to metoda wyszukiwania drzewa gry, która wykorzystuje algorytm bandyty do wybierania obiecujących węzłów do eksploracji. Gry są rozgrywane losowo, a węzły prowadzące do większej liczby zwycięstw są eksplorowane bardziej intensywnie. Algorytm bandytów utrzymuje równowagę między eksploracją węzłów o wysokich wskaźnikach wygranych a eksploracją nieznanych węzłów (i w …
1
Interaktywny dowód dla HORN-SAT?
Czy istnieje sposób, w jaki przysłowie może przekonać weryfikatora, że ​​niektóre wyrażenia HORN-SAT są zadowalające? Oczywiście może się to wydawać głupie, ponieważ istnieją algorytmy czasu liniowego dla HORN-SAT. Z drugiej strony HORN-SAT jest P-zupełny, co oznacza, że ​​nie ma algorytmów przestrzeni logów, chyba że P = L. W związku z …
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.