Teoretyczne informatyka

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

1
Obraz geometryczny za ekspanderami kwantowymi
( tutaj też nie ma odpowiedzi) (d,λ)(d,λ)(d,\lambda)νν\nuU(d)U(d)\mathcal{U}(d)|supp ν|=d|supp ν|=d|\mathrm{supp} \ \nu| =d∥EU∼νU⊗U†−EU∼μHU⊗U†∥∞≤λ‖EU∼νU⊗U†−EU∼μHU⊗U†‖∞≤λ\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}_{U \sim \mu_H} U \otimes U^{\dagger}\Vert_{\infty} \leq \lambdaμHμH\mu_Hddd przez Harrow and Low. Moje pytanie brzmi - czy ekspandery kwantowe dopuszczają jakąkolwiek interpretację geometryczną podobną do ekspanderów klasycznych (gdzie szczelina widmowa izoperymetria …

2
Rozstrzygalność labiryntu fraktalnego
Fraktalny labirynt to labirynt, który zawiera swoje kopie. Np. Następujący Mark Mark Wolf z tego artykułu : Zacznij od MINUS i przejdź do PLUS. Po wprowadzeniu mniejszej kopii labiryntu zapisz jej nazwę literową, ponieważ będziesz musiał pozostawić tę kopię przy wyjściu. Musisz wyjść z każdej zagnieżdżonej kopii labiryntu, w którą …

1
obliczanie minimalnego NFA dla DFA
Wiele lat temu słyszałem, że obliczenie minimalnego NFA (niedeterministycznego automatu skończonego) z DFA (deterministycznego) było otwartym pytaniem, w przeciwieństwie do odwrotnego kierunku, który jest znany od dziesięcioleci i jest dobrze zbadany z wydajnym algorytm. Czy ktoś wymyślił algorytm?O(nlgn)O(nlg⁡n)O(n \lg n) Szybkie wyszukiwanie dało mi ten artykuł, który dowodzi, że jest …

3
Scalenie dwóch drzew wyszukiwania binarnego
Szukam algorytmu do połączenia dwóch drzew wyszukiwania binarnego o dowolnej wielkości i zakresie. Oczywisty sposób byłoby przejść o wdrażaniu tego byłoby znaleźć całe poddrzewa, których zakres można dopasować do dowolnego węzła zewnętrznego w drugim drzewie. Jednak najgorszy czas działania tego typu algorytmu wydaje się być w kolejności, O(n+m)gdzie ni msą …

5
Zastosowania obliczeń kwantowych w świecie rzeczywistym (z wyjątkiem bezpieczeństwa)
Załóżmy, że zbudowaliśmy uniwersalny komputer kwantowy. Z wyjątkiem problemów związanych z bezpieczeństwem (kryptografia, prywatność, ...), które z obecnych problemów w świecie rzeczywistym mogą skorzystać z korzystania z niego? Interesują mnie zarówno: problemy obecnie nierozwiązywalne dla praktycznego wejścia, problemy, które są obecnie rozwiązywane, ale znaczne przyspieszenie znacznie poprawiłoby ich użyteczność.

3
Jakie jest minimalne rozszerzenie FO, które obejmuje klasę zwykłych języków?
Kontekst: relacje między logiką a automatami Twierdzenie Büchiego stwierdza, że ​​logika Monadic drugiego rzędu nad łańcuchami (MSO) przechwytuje klasę zwykłych języków. Dowód faktycznie pokazuje, że egzystencjalne MSO ( ∃MSO∃MSO\exists\text{MSO} lub EMSO ) nad łańcuchami wystarczy do przechwycenia zwykłych języków. Może to być nieco zaskakujące, ponieważ w ogólnych strukturach MSO jest …



2
Zakazane nieletnie dla ograniczonych wykresów szerokości
To pytanie jest podobne do jednego z moich poprzednich pytań. Wiadomo, że jest niedozwolonym pomniejszeniem dla wykresów szerokości co najwyżej .Kt+2Kt+2K_{t+2}ttt Czy istnieje ładnie skonstruowana, sparametryzowana, nieskończona rodzina wykresów (innych niż pełne wykresy i wykresy siatki), które są minimalnie zabronionymi nieletnimi dla wykresów o każdej szerokości. Innymi słowy, czy istnieje …


2
Sortowanie według odległości euklidesowej
jest zbiorem punktów na płaszczyźnie. Losowy punkt x ∉ S jest podany na tej samej płaszczyźnie. Zadanie to rozwiązać wszystkie y ∈ S przez euklidesową odległość pomiędzy x i y .SS.Sx∉Sx∉S.x \notin Sy∈Sy∈S.y \in Sxxxyyy Podejście no-mózg jest obliczenie odległości między i Y dla wszystkich y ∈ S , a …

2
Znaczenie ACM / IEEE w konferencji TCS
Ostatnio byłem na konferencji wspieranej przez ACM. Podczas bankietu organizatorzy konferencji opowiedzieli nam o przyszłości i przeszłości konferencji. Powiedzieli nam, że podczas edycji konferencji w 2010 roku strata wyniosła 5000 $. Pokazali nam budżet poprzedniej konferencji, gdzie mogliśmy zobaczyć, że ACM otrzymało 8000 $ (10% budżetu, jeśli dobrze pamiętam). Może …

1
Szybki splot nad małymi skończonymi polami
Jakie są najbardziej znane metody cyklicznego splotu długości na małym polu, tj. Kiedy | F | « N ? Szczególnie interesują mnie pola o stałej wielkości, a nawet F = F 2 . Doceniane są ogólne stwierdzenia i referencje dotyczące skuteczności asymptotycznej.nnn|F|≪n|F|≪n|\mathbb{F}| \ll nF=F2F=F2\mathbb{F} = \mathbb{F}_2 Tło: Niech będzie polem, …

2
Czy naprawdę można wykazać silną twardość NP za pomocą zwykłych redukcji czasu politytime?
Niedawno przeczytałem dowód, który miał wykazać, że problem był silnie NP-trudny, po prostu redukując go (w czasie wielomianowym) z problemu silnie NP-trudnego. To nie miało dla mnie żadnego sensu. Pomyślałbym, że musisz pokazać, że wszelkie liczby użyte w redukcji i przypadki problemu, do którego redukujesz, są wielomianowo ograniczone w wielkości …

1
Przybliżenie do zliczania liczby prostych ścieżek
I powiedziano, że istnieją dobre wielomianowe algorytmy czasu dla zbliżenia liczbę prostych odcinków w skierowanej wykresie począwszy od danego wierzchołka do danego zakończony wierzchołek T . Czy ktoś zna dobre referencje na ten temat?sssttt Tło: zliczanie dokładnej liczby ścieżek na ogólnym wykresie jest # P-pełne, ale mogą istnieć przybliżone wielomianowe …

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.