Teoretyczne informatyka

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

1
Czy elementarną logikę afiniczną można wykorzystać jako podstawowy system typów praktycznego języka programowania?
Elementary Affine Logic to system typów, który przechwytuje klasę terminów λ, które można zredukować w czasie elementarnym. Ponadto terminy typowe dla EAL można zredukować za pomocą abstrakcyjnego fragmentu algorytmu Lampinga, co jest dla mnie szczególnie interesujące, ponieważ badam odpowiednie kombinatory interakcji. Moje pytanie brzmi: w jaki sposób można stworzyć praktyczny …
1
Czy Memcomputing naprawdę rozwiązuje problem NP-zupełny?
Zetknąłem się z artykułem opublikowanym w Science „Memcomputing NP-zupełne problemy w czasie wielomianowym z wykorzystaniem zasobów wielomianowych i stanów zbiorowych” , co czyni niektóre dość zaskakujące twierdzenia. Memcomputing to nowy nieturingowy paradygmat obliczeń, który wykorzystuje interakcyjne komórki pamięci (w skrócie memprocessors) do przechowywania i przetwarzania informacji na tej samej platformie …
2
Statystyczna odległość między monetą jednolitą a stronniczą
Pozwolić UUU być równomiernym rozkładem nnn bitów i pozwól DDD być dystrybucją nnn bity, w których bity są niezależne, a każdy bit jest 111 z prawdopodobieństwem 1/2−ϵ1/2−ϵ1/2-\epsilon. Czy to prawda, że ​​statystyczna odległość międzyDDD i UUU jest Ω(ϵn−−√)Ω(ϵn)\Omega(\epsilon \sqrt{n}), kiedy n≤1/ϵ2n≤1/ϵ2n \le 1/\epsilon^2?
3
Definiowanie prymitywnych funkcji rekurencyjnych w stosunku do ogólnych typów danych
Pierwotne funkcje rekurencyjne są zdefiniowane ponad liczbami naturalnymi. Wydaje się jednak, że koncepcja powinna uogólnić na inne typy danych, pozwalając mówić o prymitywnych funkcjach rekurencyjnych, które mapują listy na przykład na drzewa binarne. Przez analogię częściowe funkcje rekurencyjne nad liczbami naturalnymi ładnie uogólniają się na funkcje obliczeniowe na dowolnym typie …
1
Co wiadomo na temat twardości wskaźnika chromatycznego dla ograniczonych klas grafów?
Jest ładny papier z 1991 roku, który zawiera trzy diagramy dotyczące różnych rodzin klas grafów, pokazujące, co wiadomo na temat twardości wyznaczania dla nich indeksu chromatycznego. Czy są odtąd jakieś wiadomości na ten temat? Najbardziej interesuje mnie to, co wiadomo na temat wykresów z ograniczoną liczbą chromatyczną. Moja ciekawość została …
1
Czy możliwe jest zwiększenie kwadratowego niedeterminizmu przyspieszenia obliczeń deterministycznych?
Jest to kontynuacja niedeterministycznego przyspieszenia obliczeń deterministycznych . Czy jest prawdopodobne, że niedeterminizm (lub bardziej ogólnie przemienność) pozwoliłby na ogólne kwadratowe przyspieszenie obliczeń deterministycznych? Czy są jakieś znane nieprawdopodobne konsekwencje czegoś takiego DTime(n2)⊆NTime(n)DTime(n2)⊆NTime(n)\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)?
1
Jak wybiera się pierścień wewnętrzny w algorytmie Schönhage – Strassen?
Próbowałem zaimplementować algorytm mnożenia liczb całkowitych Schönhage-Strassen, ale natknąłem się na przeszkodę w kroku rekurencyjnym. I mają wartość o bitów i Aby obliczyć . Początkowo myślałem, że pomysł takiego, że , podziel na kawałki każdy za pomocą bitów, zastosuj splot SSA podczas pracy modulo , pierścień z bitami pojemności na …
1
Dolne granice dla Frege i Extended Frege
Wikipedia [1] stwierdza, że ​​najlepiej znana dolna granica dla wielkości dowodów Frege jest kwadratowa i że nie ma znanych dolnych granic superliniowych dla liczby linii dowodów Frege. Pytania: 1) Jaka jest najbardziej znana dolna granica dla liczby linii rozszerzonych proofów Frege? 2) Jaka jest najbardziej znana dolna granica wielkości rozszerzonych …
1
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki? Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu końcach, których nigdy nie można nadpisać, a więc głowa nigdy nie może wyjść …
1
Złożoność homomorfizmu digrafa w cyklu zorientowanym
Biorąc pod uwagę stałą skierowane wykres (digrafu) The -COLORING problem decyzyjny pyta czy digrafu wejście ma homomorfizm do . (Homomorfizmem od do jest odwzorowaniem od do , która chroni łuki, to znaczy, gdy jest łukiem , a jest łukiem )DDDDDDGGGDDDGGGDDDfffV(G)V(G)V(G)V(D)V(D)V(D)uvuvuvGGGf(u)f(v)f(u)f(v)f(u)f(v)DDD Klasa problemów COLORING jest silnie związana z hipotezą dychotomii dla …
1
Sprzeczność między drugim twierdzeniem Gödela o niekompletności a własnością Church-Rosser CIC?
Z jednej strony drugie twierdzenie Gödela o niekompletności stwierdza, że ​​żadna spójna teoria formalna, która jest wystarczająco silna, aby wyrazić dowolne podstawowe stwierdzenia arytmetyczne, nie może udowodnić swojej spójności. Z drugiej strony właściwość Churcha-Rossera systemu formalnego (przepisywania) mówi nam, że jest on spójny w tym sensie, że nie wszystkie równania …
3
P / Poly a jednolite klasy złożoności
Nie wiadomo, czy NEXP jest zawarty w P / poli. Rzeczywiście udowodnienie, że NEXP nie jest w P / poli, miałoby pewne zastosowania w derandomizacji. Jaka jest najmniejsza jednolita klasa C, dla której można udowodnić, że C nie jest zawarte w P / poli? Czy wykazanie, że ko-NEXP nie jest …
1
Reżyserowane multigrafie jako minimalne automaty
Biorąc pod uwagę zwykły język L.LL na alfabecie ZAAA, jego minimalny deterministyczny automat może być postrzegany jako ukierunkowana połączona multigraf ze stałym stopniem | A ||A||A|i zaznaczony stan początkowy (poprzez zapomnienie etykiet przejść, stanów końcowych). Zachowujemy stan początkowy, ponieważ każdy wierzchołek musi być z niego dostępny. Czy odwrotność jest prawdziwa? …
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.