Teoretyczne informatyka

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

3
Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.
W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku …
4
Czy prowadzone są obecnie badania nad wdrożeniem ekstraktorów losowości?
Czy przeprowadzono badania nad implementacją konstrukcji ekstraktorów losowości? Wydaje się, że proofy ekstraktora wykorzystują Big-Oh, pozostawiając możliwość dużych, ukrytych stałych, czyniąc implementacje programowe potencjalnie nierealnymi. Trochę kontekstu: jestem zainteresowany wykorzystaniem ekstraktorów losowości jako szybkiego źródła (prawdopodobnie?) Liczb losowych do użycia w symulacjach Monte Carlo. My (grupa ETHZ Computational Physics) stronnicze …
4
Złożoność komunikacji… Klasy?
Dyskusja : Spędziłem ostatnio trochę czasu na nauce różnych rzeczy w złożoności komunikacji. Na przykład ponownie zapoznałem się z odpowiednim rozdziałem w Arora / Barak, zacząłem czytać kilka artykułów i zamówiłem książkę Kushilevitz / Nisan. Intuicyjnie chcę porównać złożoność komunikacji ze złożonością obliczeniową. W szczególności uderza mnie fakt, że złożoność …
7
Skąd możemy wiedzieć, że metody formalne działają?
Ważnym celem metod formalnych jest udowodnienie poprawności systemów, za pomocą środków automatycznych lub kierowanych przez człowieka. Wydaje się jednak, że nawet jeśli podasz dowód poprawności, NIE będziesz w stanie zagwarantować, że system nie zawiedzie. Na przykład: Specyfikacja może niepoprawnie modelować system lub system produkcyjny może być zbyt skomplikowany, aby modelować, …
2
Jawna zrównoważona macierz
Czy możliwe jest zbudowanie wyraźnej macierzy z , tak aby każda podmacierz zawiera mniej niż ?N×NN×NN \times N 0/10/10/1N1.5N1.5N^{1.5}N0.499×N0.499N0.499×N0.499N^{0.499} \times N^{0.499}N0.501N0.501N^{0.501} Lub prawdopodobnie możliwe jest zbudowanie jawnego zestawu uderzeń dla takiej właściwości. Łatwo zauważyć, że macierz losowa ma tę właściwość z prawdopodobieństwem wykładniczo bliskim . Również lemat mieszania ekspandera nie …
5
Specjalna klasa języków: języki „okrężne”. Czy to jest znane
Zdefiniuj następującą klasę języków „okrągłych” nad skończonym alfabetem Sigma. W rzeczywistości nazwa już istnieje, aby oznaczać inną rzecz, która się wydaje, stosowana w dziedzinie przetwarzania DNA. AFAICT, to inna klasa języków. Język L jest okrągła wtw dla wszystkich słów w , mamy:wwwΣ∗Σ∗\Sigma^* www należy do L wtedy i tylko wtedy, …
4
Redutacja gry permutacyjnej
Jest to powtórzenie wcześniejszego pytania . Rozważ następującą bezstronną idealną grę informacyjną między dwoma graczami, Alice i Bobem. Gracze otrzymują permutację liczb całkowitych od 1 do n. Jeśli w każdej turze wzrasta bieżąca permutacja, obecny gracz przegrywa, a drugi gracz wygrywa; w przeciwnym razie aktualny gracz usuwa jeden z numerów …
4
Czy nierozstrzygalne atrybuty P stanowią przeszkodę w podejmowaniu decyzji o P w porównaniu z NP? (odpowiedź: może)
Zadaje się pięć powiązanych pytań i oczekuje się jednej zintegrowanej odpowiedzi: P1: Czy istnieją języki które są rozpoznawane wyłącznie przez maszyny Turinga w których wykładników czasu wykonywania nie można rozstrzygnąć ?P.L.LLP.PP Q2: Czy przykłady tych maszyn Turinga mogą być skończone? P3: Czy te maszyny Turinga mogą być konkretnie tworzone? ( …
3
Badanie algorytmów / złożoności algebry liniowej
Szukam dobrej ankiety na temat algorytmów i złożoności algebry liniowej (operacje takie jak rank, inverse, wartości własne, ... dla Boolean, oraz liczby całkowite / racjonalne) z naciskiem na równoległość ( hierarchia ) i algorytmy politime. Nie mogłem znaleźć ostatniego. NCfapFp\mathbb{F}_pN.doNCNC Czy znasz dobrą ostatnią ankietę lub książkę na temat złożoności …
5
Deterministyczny algorytm równoległy do ​​idealnego dopasowania na ogólnych wykresach?
W klasie złożoności istnieją pewne domniemania, że ​​NIE występują w klasie , tj. Problemy z deterministycznymi algorytmami równoległymi. Problem maksymalnego przepływu jest jednym z przykładów. I są problemy, WIĘCEJ, że są w , ale dowód jeszcze nie został znaleziony.N C N C.P.P\mathsf{P}N C.NC\mathsf{NC}N C.NC\mathsf{NC} Znakomite dopasowanie problemem jest to jeden …
1
Czy znane są skuteczne granice ogólne w stylu Bonferroniego?
Klasycznym problemem w teorii prawdopodobieństwa jest wyrażenie prawdopodobieństwa zdarzenia w kategoriach bardziej specyficznych zdarzeń. W najprostszym przypadku można powiedzieć . Write LET'S za zdarzenie .A B A ∩ BP[A∪B]=P[A]+P[B]−P[A∩B]P[A∪B]=P[A]+P[B]−P[A∩B]P[A \cup B] = P[A] + P[B] - P[A \cap B]ABABABA∩BA∩BA \cap B Istnieją zatem pewne sposoby na powiązanie , bez zakładania …
2
Czy istnieją opisowe reprezentacje złożoności kwantowych klas złożoności?
Tytuł mniej więcej mówi wszystko, ale myślę, że mógłbym dodać trochę tła i kilka konkretnych przykładów, którymi jestem zainteresowany. Teoretycy złożoności opisowej, tacy jak Immerman i Fagin, scharakteryzowali wiele najbardziej znanych klas złożoności za pomocą logiki. Na przykład NP można scharakteryzować za pomocą zapytań egzystencjalnych drugiego rzędu; P można scharakteryzować …
2
Dlaczego modułowe potęgowanie Montgomery nie jest rozważane do stosowania w faktorowaniu kwantowym?
Powszechnie wiadomo, że potęgowanie modułowe (główna część operacji RSA) jest drogie obliczeniowo i, o ile rozumiem, preferowaną metodą jest potęgowanie modułowe Montgomery'ego . Modułowe potęgowanie jest również wyraźnie widoczne w algorytmie faktoringu kwantowego i tam również jest drogie. Więc: dlaczego modułowe potęgowanie Montgomery'ego najwyraźniej nie występuje w obecnych szczegółowych podprogramach …
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.