Teoretyczne informatyka

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

1
Jaka intuicja kryje się za logiką liniową?
Próbuję zrozumieć logikę liniową, aby lepiej zrozumieć systemy typu liniowego. Jednak kiedy czytam zasady, nie rozumiem za tym intuicji, jak to zrobiłem w logice modalnej - oznacza, że A jest wymagane, ponieważ w ramkach Kripke A jest wymagane dla każdego osiągalnego świata [ ◊ A to A jest możliwe mutatis …
1
Czy prawo wykluczenia środkowego implikuje aksjomat K w teorii typów wewnętrznych Intela Martina-Löfa?
Zastanawiam się więc, czy Prawo Wykluczonego Środka (LEM) implikuje tak zwany Axiom K w Intranice Teorii Typów Martina-Löfa. Aksjomat K stwierdza, że W rzeczywistości próbowałem udowodnić bardziej ogólne stwierdzenie, że ale po zredukowaniu do przez indukcję równości utknąłem w pierwszym problemie. Próbowałem też postępować w sprzeczności, ale wydaje się, że …
1
Entscheidungsproblem vs. Unvollständigkeitssatz (miękkie pytanie)
Pierwszy termin jest używany przez Hilberta w swojej pracy z 1928 roku, ale w późniejszej pracy Gödela to samo nazywa się Unvollständigkeitssatz („twierdzenie o niekompletności”). Dla dzisiejszych niemieckich badaczy CS wydaje się, że częściej stosuje się Unvollständigkeitssatz , a Entscheidungsproblem („problem decyzyjny”) jest nadal rozumiany, ale niekoniecznie związany z das …
1
Dlaczego wykresy refleksyjne dla parametryczności?
Patrząc na modele polimorfizmu parametrycznego, jestem ciekawy, dlaczego stosowane są kategorie wykresów refleksyjnych ? W szczególności dlaczego nie zawierają składu relacyjnego? Patrząc na modele, wszystkie wydają się potwierdzać naturalne pojęcie składu relacyjnego: x(R;S)z⟺∃y.xRy∧ySzx(R;S)z⟺∃y.xRy∧ySz x(R;S)z \iff \exists y. xRy \wedge y S z Najnowsze artykuły, które używają wykresów refleksyjnych, wydają się …
1
Jak wygląda namacalna brama kwantowa?
Czytałem opublikowane książki, artykuły i artykuły na temat obliczeń kwantowych. Odkryłem, że wszystkie materiały, które widziałem, zamiast opisywać bramę kwantową od podstawowej fizyki do abstrakcji, starają się unikać mówienia o szczegółach implementacji bram kwantowych . Najpierw zadałem sobie pytanie: czy szukam w złym obszarze, w którym dotyczy tylko matematyki formalnej? …
1
Czy podejmowanie decyzji, czy zmiana jednego wpisu zmniejsza stałą macierzy w hierarchii wielomianowej?
Rozważmy następujący problem: biorąc pod uwagę macierz M∈{−m,…,0,…,m}n×nM∈{−m,…,0,…,m}n×nM\in\{-m,\dots,0,\dots,m\}^{n\times n} , indeksy i,j∈{1,…,n}i,j∈{1,…,n}i,j\in\{1,\dots,n\} i liczbę całkowitą aaa . Wymienić M[i,j]M[i,j]M[i,j] przez i wywołać nowa macierz M . Czy p e r ( M ) > paaaM^M^\hat Mper(M)>per(M^)per(M)>per(M^)per(M)>per(\hat M) ? Czy ten problem występuje w hierarchii wielomianowej?
11 permanent 
1
Jaka jest nazwa funkcji
Niech będzie językiem if : Σ ⋆ × Σ ⋆ → Σ ⋆ funkcja na dwóch parametrach z właściwością, która dla wszystkich x i y , f zwraca element L wtedy i tylko wtedy, gdy oba x i y są elementami L :LL.Lf:Σ⋆×Σ⋆→Σ⋆fa:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starxxxyyyffafLLLxxxyyyLLL f(x,y)∈L⟺x∈L∧y∈L.f(x,y)∈L⟺x∈L∧y∈L.f(x,y)\in L \iff x\in L\wedge y\in …
1
vs
Czy ? Lub, bardziej ogólnie, czy ?NPPP=PPPNPPP=PPP\mathsf{NP^{PP}} = \mathsf{P^{PP}}NPPP⊆PPP/polyNPPP⊆PPP/poly\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}
1
Najmniejsze wyrównane do osi pole zawierające
Dane wejściowe: zbiór punktów w R 3 i liczba całkowita k ≤ n .nnnR3R3\mathbb{R}^3k≤nk≤nk \le n Dane wyjściowe: Najmniejsza obwiednia wyrównana do osi, która zawiera co najmniej tych n punktów.kkknnn Zastanawiam się, czy znane są algorytmy tego problemu. Najlepsze, co mogłem wymyślić, to czas , luźno jak następuje: brutalna siła …
1
W jaki sposób czasopisma służą społeczności TCS?
W przeszłości czasopisma były głównym sposobem rozpowszechniania i weryfikacji odkryć naukowych / matematycznych. W niektórych obszarach nadal są. Jednak w (teoretycznej) informatyce rolę tę pełnią prawie w całości konferencje i otwarte rozpowszechnianie internetowe (np. Arxiv lub osobiste strony domowe). Nadal istnieją czasopisma TCS (takie jak ToC i JACM ), ale …
1
Generowanie „nieskończonej” losowości ze stałej liczby źródeł
Ostatnio natknąłem się na artykuł Coudrona i Yuena na temat ekspansji losowości za pomocą urządzeń kwantowych. Głównym rezultatem pracy jest to, że możliwe jest wygenerowanie „nieskończonej” losowości ze stałej liczby źródeł (to znaczy liczba wygenerowanych bitów losowych zależy tylko od liczby rund protokołu, a nie od liczby źródeł ). Naiwnie …
1
Typy zależne od typu kodowanego przez Kościół w PTS / CoC
Eksperymentuję z systemami czystego typu w sześcianie lambda Barendregta, a konkretnie z najsilniejszym z nich, Rachunkiem Konstrukcji. Ten system ma rodzaje *i BOX. Dla przypomnienia, poniżej używam konkretnej składni Mortenarzędzia https://github.com/Gabriel439/Haskell-Morte-Library, która jest zbliżona do klasycznego rachunku lambda. Widzę, że możemy emulować typy indukcyjne za pomocą pewnego rodzaju kodowania podobnego …
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.