Teoretyczne informatyka

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

11
Jakie książki popularnonaukowe inspirują TCS?
Istnieje reputacja, że ​​w informatyce nie mamy książek popularnonaukowych. Oczywiście to nie do końca prawda! (W tym samym duchu listy Co Książki każdy powinien przeczytać? , Jakie dokumenty powinien każdy przeczytać? , Co każdy powinien oglądać filmy? A zainspirowana Ulubiony popularnej książce matematyka ) Jakie książki popularnonaukowe lub zasoby inspirują …
24 big-list  books 
1
Jaka jest złożoność tego problemu obejmującego?
Edycja: Najpierw źle sformułowałem moje ograniczenie (2), teraz jest poprawione. Dodałem także więcej informacji i przykładów. Z niektórymi kolegami, badającymi inne pytania algorytmiczne, byliśmy w stanie zredukować nasz problem do następującego interesującego problemu, ale nie byliśmy w stanie rozwiązać problemu jego złożoności. Problem jest następujący. Przykład: całkowita oznacza liczbę całkowitą …
1
Co jest
Jest to związane z pytaniem Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany? Niektóre naturalne problemy (-kompletne) mają świadków o długości liniowej: zadowalające przypisanie dla , ciąg wierzchołków dla itp.NPNP\mathsf{NP}SATSATSATHAMPATHHAMPATHHAMPATH Rozważ klasę złożoności „ ograniczoną do świadków o długości liniowej”. Formalna definicja tej klasy złożoności, nazwij ją …
13
Kompleksowa analiza w informatyce teoretycznej
Istnieje wiele zastosowań rzeczywistych analiz w informatyce teoretycznej, obejmujących testowanie własności, złożoność komunikacji, uczenie się PAC i wiele innych dziedzin badań. Nie mogę jednak wymyślić żadnego wyniku w TCS, który opierałby się na złożonej analizie (poza obliczeniami kwantowymi, gdzie liczby zespolone są nieodłączne w modelu). Czy ktoś ma przykład klasycznego …
2
Jaka jest najlepsza dolna granica progu tolerancji błędów w obliczeniach kwantowych?
Jest dobrze ustalone, że istnieje próg szumowy dla obliczeń kwantowych, taki że poniżej tego progu obliczenia mogą być zakodowane w taki sposób, że dają poprawny wynik z ograniczonym prawdopodobieństwem (z co najwyżej wielomianowym narzutem obliczeniowym). Próg ten zależy od zastosowanego kodowania i dokładnej natury hałasu, i często wyniki symulacji dają …
4
Rozpoczęcie pracy z rozwiązaniami SAT
Chcę zrobić pierwszy solver SAT. Znam konkurs SAT i konferencję SAT i jest tak wiele artykułów na ten temat. Jestem starterem, przytłoczonym starterem. Od czego powinienem zacząć W końcu chcę wprowadzić najnowocześniejsze rozwiązania. Chcę porady ekspertów, jak zacząć, żeby nie marnować czasu na rzeczy nieistotne zbyt wcześnie. Wielkie dzięki.
2
Złożoność obliczeniowa optyki kwantowej
W „Wymaganiu do obliczeń kwantowych” Bartlett i Sanders podsumowują niektóre ze znanych wyników obliczeń ciągłych zmiennych kwantowych w poniższej tabeli: MOJE pytanie jest trzykrotne: Czy dziewięć lat później można wypełnić ostatnią komórkę? Jeśli kolumna zostanie dodana z tytułem „Universal for BQP”, jak wyglądałaby reszta kolumny? Czy 95-stronicowe arcydzieło Aaronsona i …
5
Jaka jest maksymalna liczba trwałych małżeństw w przypadku problemu stabilnego małżeństwa?
Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy możemy stworzyć listę preferencji, która daje maksymalną liczbę trwałych małżeństw? Jaka jest górna granica takiej liczby?nnn
2
Czy typy zależne dają ci wszystko, co robi podtyp?
Typy i języki programowania skupiają się dość mocno na subtypowaniu, ale o ile wiem, subtyping nie wydaje się szczególnie fundamentalny. Czy podtypowanie daje coś więcej niż typy zależne? Praca z typami zależnymi z pewnością będzie wymagała więcej pracy, więc rozumiem, dlaczego podtypy mogą być przydatne w praktyce. Jednak bardziej interesuje …
1
Hipoteza odbudowy i częściowe 2-drzewa
Przypuszczenie o rekonstrukcji mówi, że wykresy (z co najmniej trzema wierzchołkami) są określane jednoznacznie przez ich podgrupy usunięte z wierzchołków. Ta hipoteza ma pięć dekad. Przeszukując odpowiednią literaturę, odkryłem, że następujące klasy grafów są rekonstruowalne: drzewa wykresy odłączone, wykresy, których dopełnienie jest odłączone regularne wykresy Maksymalne wykresy zewnętrzne maksymalne wykresy …
4
Jaki jest najszybszy sposób sprawdzenia włączenia zestawu?
Biorąc pod uwagę podzbiorów z .nnnS1,…,SnS1,…,SnS_1,\ldots,S_n{1,…,d}{1,…,d}\{1,\ldots,d\} Sprawdź, czy istnieją zestawy z . (Jeśli tak, znajdź przykład, jeśli nie, po prostu powiedz „nie”)Si,SjSi,SjS_i,S_jSi⊊SjSi⊊SjS_i \subsetneq S_j Trywialne rozwiązanie tego problemu polega na przejściu wszystkich par zestawów i sprawdza włączenie pary w czasie , więc całkowity czas działania wynosi . Czy ten problem …
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.