Teoretyczne informatyka

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

1
Matematyczny (kategoryczny) opis klas typów
Język funkcjonalny można postrzegać jako kategorię, w której jego obiektami są typy, a między nimi funkcjonują morfizmy. Jak pasują klasy w tym modelu? Zakładam, że powinniśmy brać pod uwagę tylko te implementacje, które spełniają ograniczenie większości klas typów, ale które nie są wyrażone w języku Haskell. Na przykład powinniśmy brać …
2
Krajobraz interaktywnych systemów dowodowych
Moje pierwsze pytanie dotyczy tego, czy charakterystyka interaktywnego systemu dowodu jest znana dla wszystkich klasycznych klas złożoności. Nazwałbym P, NP, PSPACE, EXP, NEXP, EXPSPACE, funkcje rekurencyjne i rekurencyjnie wyliczalne klasyczne (między innymi). W szczególności, czy charakterystyka interaktywnego systemu dowodu znana jest z funkcji rekurencyjnych i rekurencyjnie wyliczalnych? Wiem tylko, że …
1
Złożoność obliczeniowa mnożenia macierzy
Szukam informacji o złożoności obliczeniowej mnożenia macierzy prostokątnych macierzy. Wikipedia stwierdza, że ​​złożoność pomnożenia przez B ∈ R n × p wynosi O ( m n p ) (mnożenie podręcznika).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) Mam przypadek, w którym i n są znacznie mniejsze niż p , …
1
Czy zerowa luka integralności oznacza zerową lukę dualności dla niektórych problemów?
Wiemy, że jeśli różnica między wartościami programu liczb całkowitych i jego dualności („dualność”) wynosi zero, wówczas liniowe relaksacje programowania programu liczb całkowitych i dualność relaksacji dopuszczają rozwiązania integralne (integralność zerowa) luka"). Chcę wiedzieć, czy konwersacja się utrzymuje, przynajmniej w niektórych przypadkach. Załóżmy, że mam program liczb całkowitych 0-1 , gdzie …
1
Najlepsza złożoność zapytań algorytmu uczenia się Goldreich-Levin / Kushilevitz-Mansour
Jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Goldreich-Levin? Notatki z bloga Luca Trevisan , Lemma 3, stwierdza się jako . Czy jest to najlepiej znane pod względem zależności od n ? Będę szczególnie wdzięczny za odniesienie do źródła cytowanego!O ( 1 / ϵ4n logn )O(1/ϵ4nlog⁡n)O(1/\epsilon^4 n \log n)nnn …
1
Wystarczające warunki dla prawidłowości języka bezkontekstowego
Byłoby miło zebrać listę warunków, które sugerują, że bezkontekstowy język L jest regularny, tj. Warunki postaci: „jeśli dany CFG / PDA ma właściwość P, to jego języki są regularne” Właściwość P nie musi charakteryzować CFG generujących zwykłe języki. Ponadto P nie musi być rozstrzygalne, a P powinno „w jakiś sposób …
2
Jaki jest „najbliższy” problem hipotezy Collatza, który został pomyślnie rozwiązany?
Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej …
1
Potrzebujesz dobrego przeglądu algorytmów zwięzłej struktury danych
(już pytałem na głównej stronie , ale proszę również tutaj o lepszy zasięg, przepraszam) Ponieważ wiedziałem o zwięzłych strukturach danych, rozpaczliwie potrzebuję dobrego przeglądu najnowszych osiągnięć w tej dziedzinie. Poszukałem google i przeczytałem wiele artykułów, które mogłem zobaczyć na górze wyników wyszukiwania Google na prośby z góry mojej głowy. Nadal …
2
Złożoność optymalizacji w stosunku do grupy jednolitej
Jaka jest złożoność obliczeniowa optymalizacji różnych funkcji w grupie jednolitej ?U(n)U(n)\mathcal{U}(n) Typowe zadanie, często wynikające z teorii informacji kwantowej byłoby maksymalizując ilość typu (lub wyższych wielomiany rzędu w U ) w stosunku do wszystkich macierze jednostkowe U . Czy tego rodzaju optymalizacja jest wydajna (być może w przybliżeniu) do obliczenia, …
1
Wczesna historia niektórych wyników kompromisów czasoprzestrzennych?
Interesuje mnie wczesna historia opublikowanych wyników dotyczących kompromisów czasoprzestrzennych ogólnego przeznaczenia. W szczególności chcę wiedzieć, kto jako pierwszy opisał następujący typ algorytmu do oceny obliczeń posiadających dowolny wykres przepływu danych z O-stopniem (1), wykorzystujący przestrzeń proporcjonalną do głębokości (nie szerokości) wykresu przepływu danych (plus rozmiar danych wejściowych), wykonując prostą pierwszą …
3
Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS)
Odpowiedź: nieznana. Zadawane pytania są naturalne, otwarte i pozornie trudne; pytanie jest teraz wiki społeczności. Przegląd Pytanie ma na celu podzielenie języków należących do klasy złożoności - wraz z maszynami decyzyjnymi Turinga (TM), które akceptują te języki - na dwie uzupełniające się podklasy:PPP języki gnostyczne i bazy TM (które można …
1
Na złożoność minimalizacji przepustowości
Problem przepustowości wykresu jest zdefiniowany następująco. Biorąc pod uwagę wykres G=(V,E)G=(V,E)G=(V,E) , A układ fff z jest mapowanie jeden do jednego z wierzchołków na całkowite . Pasma określa się jakoG { 1 , … , | V | } fGGGGGG{1,…,|V|}{1,…,|V|}\{1, \ldots, |V|\}fff bw(f)=max{|f(u)−f(v)|∣{u,v}∈E}bw(f)=max{|f(u)−f(v)|∣{u,v}∈E}bw(f) = \max \{|f(u) - f(v)| \mid \{u,v\} …
2
Pytanie do # P-kompletnego dowodu stałego z Ben-Dor / Halevi
W pracy Ben-Dor / Halevi [1] podano kolejny dowód na to, że stały jest -kompletny. W dalszej części artykułu pokazano łańcuch redukcji IntPerm ∝ NoNegPerm ∝ 2PowersPerm ∝ 0/1-Perm, podczas gdy wartość stała jest zachowana wzdłuż łańcucha. Ponieważ liczba satysfakcjonujących przypisań wzoru 3SAT Φ#P#P\#PIntPerm∝NoNegPerm∝2PowersPerm∝0/1-PermIntPerm∝NoNegPerm∝2PowersPerm∝0/1-Perm\begin{equation} \text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto …
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.