Teoretyczne informatyka

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

9
Referencje dla technik proofingu TCS
Czy są jakieś odniesienia (online lub w formie książkowej), które organizują i omawiają twierdzenia TCS techniką dowodową? Garey i Johnson robią to dla różnych rodzajów konstrukcji widżetów potrzebnych do potwierdzenia kompletności NP (szczególnie w rozdziale 3 ich książki), ale zastanawiam się, czy jest coś, co traktuje techniki dowodzenia w szerszym …
9
Jaka jest różnica między niedeterminizmem a przypadkowością?
Niedawno to usłyszałem - „Maszyna niedeterministyczna to nie to samo, co maszyna probabilistyczna. Mówiąc prymitywnie, maszyna niedeterministyczna to maszyna probabilistyczna, w której prawdopodobieństwa przejścia nie są znane”. Czuję, że rozumiem, ale tak naprawdę nie. Czy ktoś mógłby mi to wyjaśnić (w kontekście maszyn lub ogólnie)? Edycja 1: Aby wyjaśnić, cytat …
4
Przykłady, w których wyjątkowość rozwiązania ułatwia znalezienie
Klasa złożoności składa się z tych N P -Problemy że może być określana przez wielomian czasu niedeterministycznych maszynie Turinga, który ma co najwyżej jedną ścieżkę akceptacji obliczeniowej. Oznacza to, że rozwiązanie, jeśli w ogóle, jest wyjątkowe w tym sensie. Uważa się wysoce nieprawdopodobne, że wszystkie U P -Problemy są P …
14
Jak praktyczna jest teoria automatów?
Zawsze istnieje sposób na zastosowanie w tematach związanych z informatyką teoretyczną. Jednak podręczniki i kursy licencjackie zwykle nie wyjaśniają, dlaczego teoria automatów jest ważnym tematem i czy nadal ma zastosowania w praktyce. Dlatego studenci mogą mieć problemy ze zrozumieniem znaczenia teorii automatów i mogą myśleć, że nie ma ona już …
5
Wyniki w teoretycznej CS niezależnej od ZFC
Zadam dość niejasne pytanie, ponieważ granica między informatyką teoretyczną a matematyką nie zawsze jest łatwa do rozróżnienia. PYTANIE: Czy znasz jakieś interesujące wyniki w CS, które są albo niezależne od ZFC (tj. Standardowa teoria zbiorów), albo które zostały pierwotnie udowodnione w ZFC (+ niektóre inne aksjomaty), a dopiero później udowodnione …
2
Aksjomaty niezbędne w informatyce teoretycznej
To pytanie jest inspirowane podobnym pytaniem o matematykę stosowaną w matematycznym przepływie i ta dokuczliwa myśl, że ważne pytania TCS, takie jak P vs. NP, mogą być niezależne od ZFC (lub innych systemów). Jako małe tło, matematyka odwrotna to projekt znalezienia aksjomatów niezbędnych do udowodnienia pewnych ważnych twierdzeń. Innymi słowy, …
2
Trudne problemy z sumą pierwiastków kwadratowych?
Suma pierwiastki problemu prosi, ponieważ dwie sekwencje i dodatnich liczb całkowitych czy suma mniejszy, równy lub większy niż suma . Status złożoności tego problemu jest otwarty; zobacz ten post, aby uzyskać więcej informacji. Problem ten powstaje naturalnie w geometrii obliczeniowej, szczególnie w problemach związanych z najkrótszymi ścieżkami euklidesowymi, i stanowi …
4
Czy ?
Wiemy, że pierwszy poziom hierarchii wielomianowej (tj. NP i co-NP) znajduje się w PP i że . Wiemy również z twierdzenia Tody, że .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Czy wiemy, czy ? Jeśli nie, to dlaczego z wyrocznią jest silniejszy niż ? Czy to możliwe, że i PP \ nsubseteq …
7
Co wiemy o możliwych do udowodnienia poprawnych programach?
Coraz większa złożoność programów komputerowych i coraz ważniejsza pozycja komputerów w naszym społeczeństwie sprawia, że ​​zastanawiam się, dlaczego nadal nie używamy zbiorowo języków programowania, w których musisz formalnie udowodnić, że kod działa poprawnie. Uważam, że termin ten jest „kompilatorem certyfikującym” (znalazłem go tutaj ): kompilatorem kompilującym język programowania, w którym …
5
Kiedy powinieneś powiedzieć to, co wiesz?
Co powinieneś zrobić, gdy zobaczysz publicznie zadane pytanie, powiedz tutaj na wymianie stosów, na które znasz odpowiedź, ponieważ patrzysz w ramach bieżącego projektu badawczego? Na przykład widzę pytanie TCS.SX, na które znam odpowiedź, ponieważ ostatnio pracowałem nad problemem. Nie skończyłem jeszcze pisać wyników i staram się uzyskać jeszcze kilka wyników, …
6
Siatka
Aktualizacja : Zestaw przeszkód (tj. „Bariera” NxM pomiędzy rozmiarami siatki do barwienia i bezbarwności) dla wszystkich 4-kolorów bez monochromatycznych prostokątów jest teraz znany . Czy ktoś ma ochotę wypróbować 5 kolorów? ;) Z teorii Ramseya wynika następujące pytanie . Rozważmy -coloring z n -by- m wykres siatki. Występuje, gdy cztery …
3
Czy implikuje ?
O ile rozumiem, program teorii geometrycznej złożoności próbuje oddzielić , udowadniając, że permament macierzy o złożonej wartości jest znacznie trudniejszy do obliczenia niż wyznacznik.VP≠VNPVP≠VNPVP \neq VNP Pytanie, które zadałem po przejrzeniu dokumentów GCT: Czy to natychmiast oznaczałoby , czy jest to tylko duży krok w kierunku tego celu?P≠NPP≠NPP \neq NP
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.