Teoretyczne informatyka

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

1
właściwości zamknięcia IP (2pfa) i AM (2pfa)
IP (2pfa) i AM (2pfa) to klasy języków rozpoznawane z błędem granicznym odpowiednio w prywatnych i publicznych wersjach monet, interaktywnych systemów dowodzenia z weryfikatorami, które są probabilistycznymi automatami skończonymi z dwukierunkową głowicą wejściową. Czy znane są jakieś właściwości zamknięcia tych klas?
1
Czy w Systemie F à la Church możemy zautomatyzować wnioskowanie o typie dla eliminacji dla wszystkich?
Pytanie jest następujące. Zasadniczo, gdy ktoś ma taki terminΛ X. tΛX.t\Lambda X.t, możemy wyeliminować forall poprzez zastosowanie tego terminu do typu, na przykład( Λ X. t ) [ T] → t [ X: = T](ΛX.t)[T]→t[X:=T](\Lambda X.t)[T]\to t[X:=T]. Załóżmy teraz, że jest to strzałka i chcemy podać jej argument, wówczas musielibyśmy …
2
Czy istnieją rodziny języków formalnych, o których wiadomo, że naprawdę można nauczyć się PAC?
Mam na myśli w szczególności rodziny języków, które dopuszczają dowolnie długie ciągi znaków - a nie koniunkcje na n bitach lub listach decyzyjnych lub jakimkolwiek innym „prostym” języku zawartym w {0,1} ^ n. Pytam o zwykłe języki „teoretyków automatycznych”, a nie teoretyków „logicznych”: coś w rodzaju języków, które można częściowo …
1
Algorytmy przeszukiwania baz danych teorii wykresów metrycznych
(Powoli) piszę recenzję Podręcznika algorytmów chemoinformatycznych dla SIGACT News. Jeden rozdział omawia bieżące implementacje oprogramowania, a wyszukiwania w bazie danych (i inne aplikacje) wydają się nie wykorzystywać tak dużej ilości informacji o wykresach, jak mogłyby. Z drugiej strony być może bardziej teoretyczne algorytmy byłyby zbyt trudne do wdrożenia. Wygląda jednak …
4
Ciągłe grupowanie
Mam więc problem z klastrowaniem danych na żywo i ciągłego przesyłania strumieniowego. Ponieważ mam stale rosnący zestaw danych, nie jestem pewien, jaki jest najlepszy sposób na wydajne i wydajne tworzenie klastrów. Wymyśliłem kilka możliwych rozwiązań, w tym: Ustawienie limitu liczby punktów danych, które mają być dozwolone, a więc za każdym …
2
Ograniczenie tempa wzrostu ceny anarchii w pojęciach równowagi
Znamy i kochamy wiele zagnieżdżonych klas koncepcji rozwiązań: PN: Równowaga Pure Nasha MN: Mixed Nash Equilibrium CE: Skorelowana równowaga CCE: kurs skorelowana równowaga. Związek między tymi zestawami jest następujący: PN⊂MN⊂CE⊂CCEPN⊂MN⊂CE⊂CCEPN \subset MN \subset CE \subset CCE Możemy rozważyć cenę anarchii w stosunku do jednej z tych koncepcji rozwiązania: najgorszy przypadek …
5
Wyniki pokazujące istnienie / nieistnienie grafów skończonych o określonych właściwościach obliczeniowych implikują pewne wyniki złożoności
Czy są jakieś znane wyniki wskazujące, że istnienie (lub nieistnienie) grafów skończonych o określonych właściwościach obliczeniowych implikuje pewne wyniki złożoności (takie jak P = NP)? Oto jeden całkowicie hipotetyczny wynik: jeśli istnieje skończony wykres z rozłożonymi krawędziami A, B, C i D, tak że wszystkie maksymalne dopasowania albo zawierają wszystkie …
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.