Teoretyczne informatyka

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

1
Prawie zawsze prawie w porządku
Szukam klasy złożoności, który dotyczy APX jako BPP dotyczy P. Już samo pytanie tutaj , ale być może będzie TCS być bardziej owocne lokalizacja odpowiedzi. Powodem tego pytania jest to, że w praktycznych problemach często trzeba znaleźć przybliżone odpowiedzi (a więc APX) z wystarczająco wysoką pewnością (a więc BPP), co …
1
Model obliczeniowy w SETH
Impagliazzo, Paturi i Calabro, Impagliazzo, Paturi wprowadzili hipotezę czasu wykładniczego (ETH) i hipotezę silnie wykładniczego czasu (SETH). Z grubsza, SETH mówi, że nie ma algorytmu, który rozwiązuje SAT w czasie . 1,99n1,99n1.99^n Zastanawiałem się, co to znaczy złamać SETH. Zdecydowanie musimy znaleźć algorytm, który rozwiązuje SAT w mniej niż krokach, …
2
Intuicja dla klasy UP
Klasa UP jest zdefiniowana jako taka: Klasa problemów decyzyjnych rozwiązanych przez maszynę NP, taką jak Jeśli odpowiedź brzmi „tak”, akceptuje dokładnie jedną ścieżkę obliczeniową. Jeśli odpowiedź brzmi „nie”, wszystkie ścieżki obliczeniowe odrzucają. Próbuję rozwinąć intuicję dla tej definicji. Czy można powiedzieć, że problemy UP są problemami z unikalnymi rozwiązaniami (np. …
7
Podręcznik zaawansowanych algorytmów
Szukam zasobów (najlepiej podręcznika) na zaawansowane tematy w algorytmach (tematy wykraczające poza to, co są omówione w podręcznikach algorytmów, takich jak CLRS i DPV). Rodzaj materiału, który można wykorzystać do nauczania tematów w kursie algorytmów, takich jak Erik Demaine i kurs Davida Kargera Advanced Algorytmy . Preferowane są zasoby, które …
2
Czy „Drugi X jest kompletny NP” oznacza, że ​​„X jest kompletny NP”?
Problem „drugiego ” to problem decydowania o istnieniu innego rozwiązania innego niż niektóre dane rozwiązanie problemu.XXX W przypadku niektórych uzupełnieniem druga wersja rozwiązania to zupełne (decydujące o istnieniu innego rozwiązania dla częściowego problemu częściowego uzupełnienia kwadratu łacińskiego), podczas gdy dla innych jest albo trywialne (Drugi NAE SAT), albo nie może …
2
Algorytm czasu liniowego znajdowania przesuniętego maks
Załóżmy, że otrzymujemy tablicę A[1..n]A[1..n]A[1..n] zawierającą nieujemne liczby całkowite (niekoniecznie różne). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w najgorszym przypadku.AAAmmmO(nlgn)O(nlg⁡n)O(n \lg n) Czy można to zrobić lepiej? Czy możemy obliczyć czasie liniowym?mmm Moje główne pytanie to powyższe. …
1
Słynny papier P = BPP Impagliazzo i Wigdersona
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji czasopisma.P = B P PP.=bP.P.\mathsf P=\mathsf{BPP} Szukam …
1
Na wykresie Izomorfizm Kompletne problemy
Jestem zainteresowany badaniem kompletnych problemów z Graph Isomorphism (GI). W artykule „Problemy wielomianowo równoważne z izomorfizmem grafowym” Kellogga S. Bootha (1979) udowodnili, że wiele podstawowych problemów jest uzupełnionych GI przy użyciu technik zastępowania krawędzi, technik kompozycji itp. Chciałbym nauczyć się kilku innych technik, które są używane w ostatnich artykułach. Czy …
1
Czy jednokierunkowe przemienne automaty z jednym licznikiem rozpoznają niektóre jednoargumentowe nieregularne języki?
Jednokierunkowe naprzemienne automaty wypychające (1APDA) mogą rozpoznać dowolny język w (Alternacja autorstwa Chandra, Kozen i Stockmeyer, 1981) . Zastępując przechowywanie w dół 1APDA przez licznik, możemy uzyskać jednokierunkowy automat na przemian z jednym licznikiem (1ACA). Moje pytanie dotyczy 1ACA w językach jednoargumentowych.D T.jaM.mi( 2O ( n ))reT.jaM.mi(2)O(n)) DTIME(2^{O(n)}) Czy 1ACA …
3
Użycie sekwencji de Bruijn do znalezienia liczby całkowitej
Sean Anderson opublikował nieco hacków zawierających algorytm Erica Cole'a, aby znaleźć liczby całkowitej bit w operacjach z mnożeniem i wyszukiwaniem.N v O ( lg ( N ) )⌈ log2)v ⌉⌈log2)⁡v⌉\lceil\log_2 v \rceilN.N.NvvvO ( lg( N) )O(lg⁡(N.))O(\lg(N)) Algorytm opiera się na „magicznej” liczbie z sekwencji De Bruijn. Czy ktoś może wyjaśnić …
3
Dwuznaczność w zwykłych i pozbawionych kontekstu językach
Rozumiem następujące twierdzenia, które są prawdziwe: Dwie różne pochodne łańcucha w danym CFG mogą czasem przypisywać to samo drzewo parsowania łańcuchowi. Kiedy w danym CFG występują pochodne jakiegoś łańcucha, które przypisują różne drzewa parsowania, CFG jest niejednoznaczny. Niektóre języki bezkontekstowe generowane przez niejednoznaczne CFG są również generowane przez jednoznaczne CFG. …
2
O wiarygodności P w porównaniu z NP
Po pierwsze, moje rozumienie twierdzenia o niekompletności Gödla (i logiki formalnej w ogóle) jest bardzo naiwne, podobnie jak moja wiedza z zakresu teoretycznej informatyki (co oznacza, że ​​tylko jeden kurs magisterski odbył się, gdy jestem jeszcze studentem), więc pytanie może być bardzo naiwny. O ile mogłem znaleźć, wiarygodność P w …
2
Trudności ze zrozumieniem algorytmu kwantowego dla problemu ukrytej podgrupy abelowej
Mam trudności ze zrozumieniem ostatnich kroków algorytmu AHSP. Niech GGG była grupą abelowa i fff jest funkcją, która ukrywa podgrupy HHH . Niech G∗G∗G^* reprezentują podwójną grupę GGG . Oto kroki algorytmu Najpierw przygotuj państwo, I=1|G|∑g∈G|g⟩|0⟩I=1|G|∑g∈G|g⟩|0⟩\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle. Następnie zastosuj kwantową wyrocznię, która ocenia fff na …
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.