Teoretyczne informatyka

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

2
Jaki paradygmat automatycznego dowodzenia twierdzeń jest odpowiedni dla formalizacji w stylu Principia Mathematica?
Posiadam książkę, która zainspirowana Principia Mathematica (PM) Russella i logicznym pozytywizmem próbuje sformalizować konkretną dziedzinę, określając aksjomaty i wydając z nich twierdzenia. Krótko mówiąc, próbuje zrobić dla swojej dziedziny to, co PM próbował zrobić dla matematyki. Podobnie jak PM, został napisany, zanim możliwe było automatyczne udowodnienie twierdzenia (ATP). Próbuję przedstawić …
4
Problemy wielomianowe w klasach grafów zdefiniowanych przez zabronione indukowane cykliczne podgrupy
Skrzyżowane z MO . Niech CCC będzie klasą grafu zdefiniowaną przez skończoną liczbę zabronionych indukowanych podrożników, z których wszystkie są cykliczne (zawierają co najmniej jeden cykl). Czy istnieją problemy związane z grafem trudnym dla NP, które można rozwiązać w czasie wielomianowym dla CCC innego niż Clique i Clique? Jeśli dobrze …
1
Ustaw osłonę z ograniczonym rozmiarem przecięcia
Problem pokrycia zestawu jest więc trywialny, jeśli żaden z zestawów kandydujących się nie przecina. Co jednak, jeśli rozmiar przecięcia dowolnej pary zestawów kandydujących wynosił co najwyżej 1? Czy ten problem jest trudny NP? Byłbym wdzięczny za każdy wgląd. Dzięki, Garrett
11 set-cover 
1
Typy W vs typy indukcyjne
Teoria typów Martina-Löfa wykorzystuje typy W do definiowania struktur indukcyjnych, takich jak liczby całkowite, listy itp. Jednak rachunek konstrukcji indukcyjnych nie używa ich w ten sam sposób, typy indukcyjne wydają się być bardziej podobne do schematów aksjomatycznych. Czy te dwa podejścia są równoważne (wydają się być)? Czy są jakieś filozoficzne …
3
Czy istnieją niekonstruktywne dowody na istnienie „małych” maszyn Turinga / NFA?
Po przeczytaniu powiązanego pytania dotyczącego niekonstruktywnych dowodów istnienia algorytmów, zastanawiałem się, czy istnieją metody pokazania istnienia „małych” (powiedzmy, stanowych) maszyn obliczeniowych bez ich budowania. Formalnie: załóżmy, że otrzymaliśmy język i naprawiliśmy jakiś model obliczeniowy (NFA / maszyna Turinga itp.).L ⊆ Σ∗L⊆Σ∗L\subseteq \Sigma^* Czy istnieją jakieś niekonstruktywne wyniki istnienia pokazujące, że …
3
Na czym polegają badania w dziedzinie informatyki teoretycznej?
Staram się zrozumieć, co jest zaangażowane w teoretyczne badania informatyczne. Czym zajmują się informatycy teoretyczni? Wiem, że znaczna ilość czasu poświęcana jest na nauczanie, nadzorowanie doktorantów, ubieganie się o fundusze i obowiązki departamentalne. Odkładając je na bok, jak spędzasz czas na badaniach? Jakie są najważniejsze czynności, które zazwyczaj wykonujesz? Zgaduję, …
1
Naturalne transformacje i parametryczność
W twierdzeniach za darmo! , Wadler mówi, że charakterystykę parametryczności można wyrazić ponownie w kategoriach luźnych naturalnych przekształceń i będzie to przedmiotem kolejnego artykułu. Do którego referatu się odnosi? W znanym mi kategorycznie podejściu do paramteryczności stosuje się transformacje dinaturalne, jak w polimorfizmie funkcjonalnym Bainbridge, Freyda, Scedrowa i PJ Scotta. …
1
Jakieś dowody na to, że Linial, Shraibman niższa granica złożoności komunikacji kwantowej nie jest ścisła?
O ile mi wiadomo, dolna granica normy faktoryzacji podana przez Liniala i Shraibmana jest zasadniczo jedyną dolną granicą znaną ze złożoności komunikacji kwantowej (lub przynajmniej obejmuje wszystkie inne). Czy są jakieś dowody przeciwko ścisłości tego powiązania? Ograniczona normą faktoryzacji (zwana także granicą ), o której mówię, to Twierdzenie 13 Linial, …
1
Biorąc pod uwagę
Oto problem o smaku podobnym do nauki junt: Dane wejściowe: Funkcja , reprezentowana przez wyrocznię członkowską, tzn. Wyrocznię, która dała , zwraca .x f ( x )fa: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\}xxxfa( x )f(x)f(x) Cel: Znajdź podmoduł S.SS o wartości { …
2
Jak mogę obliczyć węzły?
Czy istnieje udokumentowany sposób obliczania węzłów? (obwody osadzone w trójwymiarowej przestrzeni euklidesowej). Mam na myśli typ danych, który je reprezentuje, oraz algorytm określający, czy dwa wystąpienia typu danych reprezentują ten sam węzeł. Jeśli odpowiedź jest pozytywna, co ze złożonością tego problemu?
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.