Teoretyczne informatyka

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

1
Dlaczego Martin-Löf potrzebował stworzyć intuicyjną teorię typów?
Czytałem o Intuitionistic Type Theory (ITT) i to ma sens. Ale staram się zrozumieć, dlaczego „dlaczego” zostało stworzone? Intuicyjna logika (IL) i prosty typ rachunek (STLC) i teoria typów ogólnie poprzedzają samo istnienie samego Martina-Löfa! Wydaje się, że w STLC można zrobić wszystko, co jest możliwe w ITT (mogę się …
2
Naturalne kompletne problemy na wyższych poziomach hierarchii
-hierarchy hierarchia klas złożoność w sparametryzowanej złożoności patrz Zoo złożoność definicje. Alternatywna definicja definiuje przy użyciu ważonej definiowalności Fagina dla logiki pierwszego rzędu, patrz podręcznik Fluma i Grohe .W [ t ] W [ t ] Π tWW\mathsf{W}W[t]W[t]\mathsf{W}[t]W[t]W[t]\mathsf{W}[t]ΠtΠt\Pi_t Dla najniższych klas i , znanych jest wiele naturalnych kompletnych problemów, np. …
1
Dowody poprawności klasycznych Paxos i Fast Paxos
Czytam artykuł „Fast Paxos” autorstwa Leslie Lamport i utknąłem z dowodami poprawności zarówno klasycznych Paxos, jak i Fast Paxos. Aby zachować spójność, wartość wybrana przez koordynatora w fazie 2 a w rundzie i powinna spełniaćvvv2 a2a2ajaii Dla dowolnej rundy j < i żadna wartość inna niż v nie była lub …
3
Przykłady problemów, w których algorytmy wykładnicze działają szybciej niż algorytmy wielomianowe dla praktycznych rozmiarów?
Czy znasz jakieś problemy (najlepiej przynajmniej nieco dobrze znane), w których dla praktycznego rozmiaru problemu algorytm wykładniczy działa znacznie szybciej niż najbardziej znany odpowiednik czasu wielomianowego. Załóżmy na przykład, że problem ma praktyczny rozmiar * i istnieją dwa znane algorytmy: jeden to a drugi to dla pewnej stałej . Oczywiście …
1
Trudne problemy z rozszerzalnością
W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w trudny. Na przykład twierdzenie Koniga-Halla stwierdza, że ​​wszystkie sześcienne dwustronne wykresy można pokolorować …
1
Kolejny wariant PARTYCJI
Mam redukcję następującego problemu z partycją do pewnego problemu z planowaniem: Dane wejściowe: lista liczb całkowitych dodatnich w kolejności nie malejącej.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Pytanie: Czy istnieje wektor taki, że(x1,…,xn)∈{−1,1}n(x1,…,xn)∈{−1,1}n(x_1,\ldots,x_n)\in\{-1,1\}^n ∑i=1naixi=0and∑i=1naixi=0and\sum_{i=1}^na_ix_i=0\qquad\text{and} ∑i=1kaixi⩾0for all k∈{1,…,n}∑i=1kaixi⩾0for all k∈{1,…,n}\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\} Bez drugiego warunku jest to po prostu PARTYCJA, a więc NP-twardy. Ale drugi …
1
Rozróżnianie dwóch monet
Powszechnie wiadomo, że złożoność odróżnianie się stronniczy monetę z jednego sprawiedliwego jest θ ( ε - 2 ) . Czy istnieją wyniki dla odróżnienia monety p od monety p + ϵ ? Widzę, że dla specjalnego przypadku p = 0 złożoność będzie wynosić ϵ - 1 . Mam przeczucie, że …
1
Kariery dla teoretycznych informatyków
Jakie są typowe kariery dla informatyków teoretycznych (osoby z dyplomem informatyki teoretycznej)? Jakie branże i instytucje szukają teoretycznej wiedzy informatycznej? Jakie kariery zwykle postrzegają informatycy teoretyczni?
1
Testowanie izomorfizmu grafów asymetrycznych
Czytając pytanie Przykłady gdzie wyjątkowość rozwiązania sprawia, że łatwiej znaleźć , nowy (? Łatwiej) pytanie przyszło mi do głowy: Właściwie nie wiemy, czy izomorfizm grafów ( ) problem jest w P .GIGIGIPPP Ale co się stanie, jeśli założymy, że zarówno i G 2 są asymetryczne (tj. Oba mają jedynie trywialny …
2
Możliwe do przewidzenia luki między złożonością drzewa decyzyjnego a „prawdziwą” złożonością
Tytuł jest trochę mylący: ale mam nadzieję, że pytanie nie brzmi: Grønlund and Pettie Nowa wynik pokazujący, że 3SUM ma tylko drzewo decyzyjne złożoność got me zastanawiasz się:O ( n3 / 2)O(n3/2)O(n^{3/2}) Czy istnieje prosty przykład problemu ze złożonością drzewa decyzyjnego ale który dopuszcza dolną granicę (w bardziej szczegółowym modelu) …
3
Dowód nierozstrzygalności, a nie redukcja problemu zatrzymania
Zwykłym sposobem udowodnienia nierozstrzygalności jest redukcja problemu RE-zupełnego, takiego jak problem zatrzymania, trafność w logice pierwszego rzędu, spełnienie równań diofantycznych itp. Wiadomo, że istnieją rekurencyjnie wyliczalne, ale nierozstrzygalne problemy, które nie są uzupełniane ponownie, ale są to sztuczne konstrukcje (to znaczy zestawy, które zostały zdefiniowane tylko w celu pokazania tego …
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.