Teoretyczne informatyka

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

1
Jakie mamy dowody na ?
Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie. Jakie mamy dowody na ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną ścieżkę akceptacji w instancjach „tak” i brak ścieżki akceptacji w instancjach „nie”.UPUP\mathsf{UP} Oczywiście , …
2
Porównanie dwóch algorytmów dla problemu 3SUM w stosunku do liczb całkowitych
Artykuł „Algorytmy subkwadratowe dla 3SUM” autorstwa Ilyi Baran, Erika D. Demaine'a, Mihai Patrascu ma następującą złożoność 3SUM problemów: otrzymuje listę L.L.L z liczb całkowitych czy istnieją taki sposób, żennnx , y, z∈ L.x,y,z∈L.x,y,z \in Lx + y= z.x+y=z.x+y=z. Twierdzą oni, „W przypadku standardowego tekstu z pamięci RAM bitowych słów, otrzymujemy …
2
Klasy wykresów, w których problemy cyklu Hamiltoniana i ścieżki Hamiltoniana mają różną złożoność
Podczas przeszukiwania Systemu informacji o klasach grafów i ich inkluzjach znalazłem kilka klas grafów, dla których problem cyklu Hamiltoniana jest NP-kompletny, natomiast złożoność problemów ścieżki Hamiltonian NIE jest znana. Niektóre z tych klas to dwuczęściowe wykresy o maksymalnym stopniu 3, wykresy o maksymalnym stopniu 3 i 2 połączone sześcienne wykresy …
2
Problem z izomorfizmem grafów
Robię przegląd literatury na temat problemu izomorfizmu grafów. Większość artykułów, które czytam, są napisane przez EM Luksa i Laszlo Babai. W tych pracach wykorzystano znajomość teorii grup i teorii złożoności na wysokim poziomie. Ponieważ jestem nowy w tej dziedzinie, wiele rzeczy nie jest dla mnie oczywistych. Czy ktoś może mi …
3
W jakiej klasie są algorytmy losowe, które mają błąd z dokładnie 25% szansą?
Załóżmy, że rozważam następujący wariant BPP, który pozwala nam nazywać się E (xact) BPP: Język jest w EBPP, jeśli istnieje wielomianowy losowy czas TG, który akceptuje każde słowo z prawdopodobieństwem dokładnie 3/4 i każde słowo nie w język z prawdopodobieństwem dokładnie 1/4. Oczywiście EBPP jest zawarty w BPP, ale czy …
1
Kariera w informatyce teoretycznej
Obecnie jestem uczniem szkoły średniej, interesuję się informatyką teoretyczną i matematyką stosowaną. Nauczyłem się algebry liniowej, rachunku różniczkowego i matematycznego. Mam naiwne przekonanie, że aby pisać lepsze algorytmy, trzeba znać tyle matematyki, ile się da, ponieważ można się uczyć o nowych strukturach, a następnie używać tych struktur do tworzenia bardziej …
5
Dlaczego ekonomiści powinni dbać o złożoność obliczeniową
Czy próbując przekonać ekonomistów o znaczeniu teorii złożoności w druku, istnieje standardowe odniesienie do cytowania? Znam post na blogu Noama Nisana , ankietę Tima Roughgarden i rozdział 11 eseju Scotta Aaronsona . Te posty są dostępne dla informatyków, ale nie używają języka ekonomistów i nie są publikowane w miejscach zwykle …
1
Złożoność problemu pokrycia interwałów
Rozważmy następujący problemQQQ : Otrzymujemy liczbę całkowitą i przedziałów z . także liczb całkowitych . Zadanie polega na wybraniu minimalnej liczby przedziałównnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq l_i\leq r_i\leq 2n2n2n2nd1,…,d2n≥0d1,…,d2n≥0d_1,…,d_{2n}\geq 0 , że dla każdego i = 1 , ... , 2 n , co najmniej d ı odstępach zawierających całkowitą i są zaznaczone.[li,ri][li,ri][l_i,r_i]i=1,…,2ni=1,…,2ni=1,…,2ndidid_iiii Nietrudno …
1
Jaka jest kategoryczna semantyka podtypów?
Począwszy od Curry-Howarda-Lambka, pojawiła się niezła trójca typów teorii, logiki i kategorii. Jestem ciekawy, jaką semantyczną kategorię uzyskujesz, gdy dodajesz (przymus) podtyp do teorii typów - wygląda na to, że nie zostało to zbytnio zbadane, jeśli w ogóle. Ogólnie rzecz biorąc, dodanie przymusowego podtypu do teorii typów nie rujnuje jego …
1
Złożoność próbkowania (w przybliżeniu) transformaty Fouriera funkcji boolowskiej
Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1±1\pm 1 Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli wybranie x zgodnie z . (Znormalizowane w razie potrzeby …
1
Jaka jest złożoność tego problemu kolorowania krawędzi?
Ostatnio spotkałem następujący wariant kolorowania krawędzi. Biorąc pod uwagę połączony niekierowany wykres, znajdź kolorystykę krawędzi, która wykorzystuje maksymalną liczbę kolorów, jednocześnie spełniając ograniczenie, że dla każdego wierzchołka krawędzie padające na v używają co najwyżej dwóch kolorów.vvvvvv Po pierwsze sądzę, że problem jest trudny do rozwiązania. Klasyczne twarde proofy NP na …
3
Konstruktywnie wydajne algorytmy bez sprawdzania poprawności i wydajności
Szukam naturalnych przykładów wydajnych algorytmów (tj. W czasie wielomianowym) ul ich poprawność i skuteczność można konstruktywnie udowodnić (np. w lub ), alePRAPRAPRAHAHAHA nie jest znany żaden dowód wykorzystujący tylko wydajne koncepcje (tzn. nie wiemy, jak udowodnić ich poprawność i wydajność w lub ).TV0TV0TV^0S12S21S^1_2 Mogę samodzielnie tworzyć sztuczne przykłady. Chcę jednak …
3
Czy istnieje koncepcja czegoś takiego jak funktony kooperacyjne siedzące między comonadami i funktorami?
Każda monada jest również funktorem aplikacyjnym, a każdy funktor aplikacyjny jest funktorem. Ponadto każdy comonad jest funktorem. Czy istnieje podobna koncepcja między comonadami i funktorami, coś w rodzaju funktora kooperacyjnego i jakie są jego właściwości? \begin{array}{c} \end{array} Functors↑Applicative functors↑MonadsFunctors↑???↑ComonadsFunctorsFunctors↑↑Applicative functors???↑↑MonadsComonads\begin{array}{cc} \mbox{Functors} & & \mbox{Functors} \\ \uparrow & & \uparrow \\ …
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.