Teoretyczne informatyka

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

1
Jaki jest „prawdziwy” powód, dla którego IP = PSPACE nie powoduje relatywizacji?
OOOcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf IP}^OcoNPO⊆PSPACEOcoNPO⊆PSPACEO{\sf coNP}^O \subseteq {\sf PSPACE}^OOOO Jednak widziałem tylko kilka osób, które wyjaśniają „bezpośrednio”, dlaczego wynik nie jest relatywizowany, a typową odpowiedzią jest „arytmetyzacja”. Po sprawdzeniu dowodu IP = PSPACE ta odpowiedź nie jest fałszywa , ale nie jest dla mnie zadowalająca. Wydaje się, że „prawdziwy” powód …
2
Czy JSON jest językiem zwykłym?
Zastanawiałem się, czy specyfikacja JSON definiuje zwykły język. Wydaje się to dość proste, ale nie jestem pewien, jak sam to udowodnić. Powodem, dla którego pytam, jest to, że zastanawiałem się, czy można użyć wyrażeń regularnych, aby skutecznie przetworzyć JSON. Czy ktoś z wystarczającą liczbą przedstawicieli może dla mnie utworzyć tagi …
2
Jaka jest złożoność przestrzeni przy obliczaniu wartości własnych?
Szukam pracy ankietowej lub książki obejmującej wyniki dotyczące złożoności przestrzeni typowych operacji algebry liniowej, takich jak ranga macierzy, obliczanie wartości własnych itp. Podkreślam część „złożoności przestrzeni”, która oznacza złożoność przestrzeni pracy, a nie złożoność czasu, ponieważ łatwiej jest prześledzić wyniki czasowe. Doceniam wszelkie odniesienia w tej sprawie. Dzięki.
5
W jakim stopniu „zaawansowana matematyka” jest potrzebna / przydatna w badaniach nad AI?
Obecnie studiuję matematykę. Jednak nie sądzę, żebym chciał zostać zawodowym matematykiem w przyszłości. Zastanawiam się nad wykorzystaniem mojej wiedzy z matematyki do badań nad sztuczną inteligencją. Nie jestem jednak pewien, ile kursów matematyki powinienem odbyć. (I które kursy teorii CS powinienem śledzić.) Z Quora dowiedziałem się, że przedmioty Algebra liniowa, …
3
Jak mówić o teorii
Zdaję sobie sprawę, że może to być kontrowersyjne pytanie, ale wydawało się, że to właściwe miejsce do zadawania pytań. Proszę mnie przekierować, jeśli nie. Tło jest takie, że jestem „praktykiem” (doktorantem, nie studiuję teorii CS), ale mam uzasadnione podstawy w algorytmach licencjackich i matematyce. Niemniej jednak dyskusje z teoretykami są …
2
Decydowanie, czy jednolity język kontekstowy jest prawidłowy
To dobrze znany wynik, że pytanie Czy gramatyka bezkontekstowa generuje zwykły język? jest nierozstrzygalny. Jednak staje się to rozstrzygalne na podstawie jednoznacznego alfabetu, po prostu dlatego, że w tym przypadku klasy języków bezkontekstowych i zwykłych pokrywają się. Moje pytanie polega na tym, aby wiedzieć, co dzieje się w przypadku jednoargumentowych …
4
Chaos i pytanie
Interesuje mnie nauka powiązań między „chaosem”, a szerzej, systemami dynamicznymi, a pytaniem . Oto przykład rodzaju literatury, której szukam:P.= NP.P.=N.P.P{=}NP Ercsey-Ravasz, Mária i Zoltán Toroczkai. „Twardość optymalizacji jako przejściowy chaos w analogicznym podejściu do satysfakcji z ograniczeń”. Nature Physics 7, no. 12 (2011): 966–970. ( Link do czasopisma ). Czy …
2
Dowód, że górne granice obwodu dla
W oficjalnym opisie problemu Clay dla P kontra NP stwierdzono, że wynikałoby z pokazania, że ​​„każdy język w E [klasa języków rozpoznawalnych w czasie wykładniczym z deterministyczną maszyną Turinga] może być obliczony przez rodzinę obwodów boolowskich < B n > , tak że co najmniej jedno n , B n …
2
Złożoność odzyskiwania macierzy sąsiedztwa z jej kwadratu
Interesuje mnie następujący problem: Biorąc pod uwagę macierz , czy istnieje niekierowany wykres na n wierzchołkach, których macierz przylegania do kwadratu jest tą macierzą?n × nn×nn\times nnnn Czy znana jest złożoność obliczeniowa tego problemu? Uwagi: Oczywiście może być również sformułowany jako problem wyszukiwania, w którym podane są macierzy do A …
1
Algorytmiczne zalety szerokości ścieżki w porównaniu do szerokości
Treewidth odgrywa ważną rolę w algorytmach FPT, częściowo dlatego, że wiele problemów jest FPT parametryzowanych przez treewidth. Powiązanym, bardziej ograniczonym pojęciem jest szerokość ścieżki. Jeśli wykres ma szerokość ścieżki , ma również szerokość co najwyżej , podczas gdy w kierunku przeciwnym, szerokość oznacza tylko szerokość ścieżki co najwyżej a to …
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.