Teoretyczne informatyka

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

4
Loteria, którą możesz przekonać, że jest uczciwa
(Przepraszam, jeśli jest to dobrze znane.) Chciałbym podać jakiś przedmiot jednemu z agentów, aby agent j otrzymał element z prawdopodobieństwem p i . Czy istnieje narzędzie kryptograficzne (lub inne), aby każdy agent (a nawet każdy obserwator) był w stanie przekonać się, że losowe losowanie rzeczywiście było uczciwe?kkkjjjpipip_i
1
Dlaczego zwykłe języki nazywane są „zwykłymi”?
Dlaczego języki regularne (i te wyrażenia regularne) nazywane są „regularnymi”? Dużo prawidłowości występuje również w językach bezkontekstowych i innych rodzajach języków. Przypuszczam, że na początku zastosowano przymiotnik „zwykły” w celu odróżnienia tego rodzaju języków od innych „nieregularnych” lub w jakiś sposób nienormalnych języków. Jeśli tak, to gdzie te inne typy …
2
Marzyłem o strukturze danych, czy ona istnieje?
Nie udało mi się znaleźć tej struktury danych, ale nie jestem ekspertem w tej dziedzinie. Struktura implementuje zestaw i jest w zasadzie szeregiem porównywalnych elementów z niezmiennikiem. Niezmiennikiem jest to (zdefiniowane rekurencyjnie): Tablica o długości 1 jest tablicą scalającą. Tablica o długości 2 ^ n (dla n> 0) jest tablicą …
5
Dowody kwantowe klasycznych twierdzeń
Interesują mnie przykłady problemów, w których twierdzenie, które pozornie nie ma nic wspólnego z mechaniką / informacją kwantową (np. Mówi coś o obiektach czysto klasycznych), może jednak zostać udowodnione za pomocą narzędzi kwantowych. Badanie Kwantowe dowody dla klasycznych twierdzeń (A. Drucker, R. Wolf) podaje ładną listę takich problemów, ale na …
4
Złożoność zastosowania permutacji w miejscu
Ku mojemu zaskoczeniu nie udało mi się znaleźć artykułów na ten temat - prawdopodobnie przeszukałem niewłaściwe słowa kluczowe. Mamy więc tablicę czegokolwiek i funkcję na jej indeksach; jest permutacją.ffffff Jak zmienić kolejność tablic zgodnie z pamięcią i czasem działania tak blisko i jak to możliwe?fffO(1)O(1)O(1)O(n)O(n)O(n) Czy są jakieś dodatkowe warunki, …
2
Złożoność właściwości topologicznych.
Jestem informatykiem biorącym udział w kursie na temat topologii (posypka topologii punktowej mocno przyprawionej teorią kontinuum). Zainteresowały mnie problemy decyzyjne testujące opis przestrzeni (uproszczeniem) dla właściwości topologicznych; zachowane do homeomorfizmu. Wiadomo na przykład, że określenie rodzaju węzła znajduje się w PSPACE i jest NP-twarde. (Agol 2006; Hass, Lagarias, Pippenger 1999) …
1
Pomoc algorytmu faktoringu Shora
Mam mały problem z pełnym zrozumieniem ostatnich kroków algorytmu faktoringu Shora. Biorąc pod uwagę którą chcemy uwzględnić, wybieramy losowy x, który ma porządek r .NNNxxxrrr Pierwszy krok obejmuje skonfigurowanie rejestrów i zastosowanie operatora Hadamard. W drugim kroku stosuje się operator liniowy. Trzeci krok jest mierzony drugim rejestrem (uważam, że ten …
1
Dobre kody dekodowalne przez obwody liniowe?
Szukam kodów korygujących błędy następującego typu: kody binarne o stałej szybkości, dekodowalny z pewnej stałej części błędów za pomocą dekodera możliwego do zaimplementowania jako logiczny obwód o rozmiarze , gdzie N jest długością kodowania.O ( N)O(N)O(N)N.NN Trochę tła: Spielman, w liniowych kodowalnych i dekodowalnych kodach korygujących błędy , dał kody …
1
Izometryczne osadzanie L2 w L1
Wiadomo, że biorąc pod uwagę podzbiór (to znaczy, biorąc pod uwagę punktów w z odległością euklidesową), możliwe jest osadzenie ich izometrycznie w \ ell ^ {n \ wybierz 2 } _1 .nnnℓd2ℓ2d\ell_2^dnnnRdRd{\mathbb R}^dℓ(n2)1ℓ1(n2)\ell^{n\choose 2}_1 Czy izometria jest obliczalna w (ewentualnie losowym) czasie wielomianowym? Ponieważ istnieją problemy z precyzją skończoną, dokładne …
6
Jak uzyskać „intuicję fizyczną” dla wyników w TCS?
Przepraszam, jeśli to pytanie jest trochę niejasne, ale jestem ciekawy, jak odnoszący sukcesy badacze „odczuwają” wyniki w TCS. Na przykład algebra liniowa może być rozumiana geometrycznie lub w kategoriach jej fizycznych interpretacji (wektory własne można traktować jako „punkty stabilne” w systemie) itp. Intuicyjne jest również, że istnieje protokół IP dla …
2
Czy można sprawdzić, czy sekwencja istnieje w czasie wielomianowym w następującym problemie?
Przez jakiś czas myślałem o następującym problemie i nie znalazłem rozwiązania wielomianowego. Tylko brutalne źródło. Próbowałem też zredukować problem NP-Complete bez powodzenia. Oto problem : Masz posortowany zestaw {(A1,B1),(A2,B2),…,(An,Bn)}{(A1,B1),(A2,B2),…,(An,Bn)}\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\} par dodatnich liczb całkowitych. (Ai,Bi)&lt;(Aj,Bj)⇔Ai&lt;Aj∨(Ai=Aj∧Bi&lt;Bj)(Ai,Bi)&lt;(Aj,Bj)⇔Ai&lt;Aj∨(Ai=Aj∧Bi&lt;Bj)(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i …
2
Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi
Peter Shor pokazał, że dwa z najważniejszych problemów pośrednich NP, faktoring i dyskretny log, są w BQP. Natomiast najbardziej znany algorytm kwantowy dla SAT (poszukiwanie Grovera) zapewnia jedynie kwadratową poprawę w porównaniu z klasycznym algorytmem, co sugeruje, że problemy z całkowitą NP są wciąż trudne do rozwiązania na komputerach kwantowych. …
6
Które problemy z SAT są łatwe?
Jakie są „łatwe regiony” dla satysfakcji? Innymi słowy, wystarczające warunki, aby niektóre solver SAT mógł znaleźć zadowalające zadanie, pod warunkiem, że istnieje. Jednym z przykładów jest sytuacja, w której każda klauzula dzieli zmienne z kilkoma innymi klauzulami, ze względu na konstruktywny dowód LLL, czy są jakieś inne wyniki w tym …
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.