Teoretyczne informatyka

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

1
Mieszanie hasła przy użyciu NP pełne problemy
Powszechnie używane algorytmy haszujące hasła działają dzisiaj tak: Zasol hasło i wprowadź je do KDF. Na przykład przy użyciu PBKDF2-HMAC-SHA1 proces mieszania hasła toDK = PBKDF2(HMAC, Password, Salt, ...) . Ponieważ HMAC jest 2-okrągłym skrótem z wyściełanymi klawiszami, a SHA1 szereg permutacji, przesunięć, rotacji i operacji bitowych, zasadniczo cały proces …
1
Jaka jest złożoność tego problemu z grafem?
Biorąc pod uwagę prosty niekierowany wykres GGG , znajdź podzbiór A≠∅A≠∅A\neq \emptyset wierzchołków, taki jak dla dowolnego wierzchołka x∈Ax∈Ax\in A co najmniej połowa sąsiadów xxx również znajduje się w AAA i rozmiar AAA jest minimalny. Oznacza to, że szukamy gromady, w której co najmniej połowa sąsiedztwa każdego wewnętrznego wierzchołka pozostaje …
2
Czy przecięcie matroidów graficznych
Wiadomo, że przecięcie trzech ogólnych matroidów jest NP-twarde ( źródło ), co odbywa się poprzez redukcję z cyklu Hamiltona. Redukcja wykorzystuje jedną matroidę graficzną i dwie matroidy łączności. Specjalny przypadek problemu, nad którym pracuję, można rozwiązać, przecinając wiele matroidów graficznych, ale nie udało mi się ustalić, czy problem występuje w …
1
Czy BPP vs. P to prawdziwy problem po tym, jak wiemy, że BPP leży w P / poly?
My wiemy (teraz około 40 lat, dzięki Adleman, Bennet Gill), że włączenie BPP ⊆⊆\subseteq P / poly, i jeszcze silniejszy BPP / poli ⊆⊆\subseteq P / poli trzymaj. „/ Poly” oznacza, że ​​pracujemy nierównomiernie (osobny obwód dla każdej długości wejściowej nnn ), podczas gdy P bez tego „/ poly” oznacza, …
1
Jak cytować nowy wynik izomorfizmu grafu Babai?
Niedawno Babai opublikował artykuł na temat STOC 2016, twierdząc, że izomorfizm grafów można rozwiązać w czasie quasipolynomialnym. Na początku 2017 r. Babai wycofał roszczenie quasipolomomial z powodu poważnych błędów wykrytych przez Haralda Helfgotta. Jak wyjaśnił sam Babai, ta wada sprawia, że ​​poprawa jest bardziej skromna pod względem czasu działania. Około …
1
Kwadratowy związek między przestrzenią niedeterministyczną a deterministyczną?
Twierdzenie Savitcha pokazuje, że NSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2) dla wszystkich wystarczająco dużych funkcji fff , i udowodnienie, że jest ciasno, było otwartym problemem od dziesięcioleci . Załóżmy, że podchodzimy do problemu z drugiego końca. Dla uproszczenia załóżmy logiczny alfabet. Ilość miejsca wykorzystywanego przez TM do decydowania o języku obliczeniowym jest często …
2
„Prawie sortujące” liczby całkowite w czasie liniowym
Interesuje mnie sortowanie tablicy dodatnich wartości liczb całkowitych w czasie liniowym (w modelu pamięci RAM z jednolitą miarą kosztów, tj. Liczby całkowite mogą mieć wielkość logarytmiczną, ale przyjmuje się, że operacje arytmetyczne na nich przyjmą czas jednostkowy). Oczywiście nie jest to możliwe w przypadku algorytmów sortowania opartych na porównaniu, więc …
1
Charakterystyka dla której nie jest CFL?
Jest to standardowy dowód w kursach z automatami, że dla i że nie jest językiem bezkontekstowym.L=Σ⋆L=Σ⋆L = \Sigma^\star|Σ|≥2|Σ|≥2|\Sigma| \ge 2S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} Prawdą jest również, że dla każdego skończonego , jest skończone (a zatem CFL). Zgaduję, że jest nieskończony i regularny nie jest „wystarczający”, aby nie …
3
Kategoria „maszyn Turinga”?
Zastrzeżenie: Wiem bardzo mało o teorii złożoności. Przepraszam, ale tak naprawdę nie ma sposobu, aby zadać to pytanie bez (strasznie) zwięzłego: Jakie powinny być morfizmy w „kategorii” maszyn Turinga? Jest to oczywiście subiektywne i zależy od interpretacji teorii, więc odpowiedź na to pytanie powinna idealnie dać pewne dowody i uzasadnienie …
3
Rozdzielanie klas czasowych
Mój student ostatnio zadał następujące pytanie: DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq DTIME(g(n)).h(n)h(n)h(n)DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))? Prawdopodobnie można to udowodnić, konstruując jeśli są konstruowalne w czasie. Ale ogólnie uważam, że powinno to być fałszem podobne do .h(n)h(n)h(n)f,gf,gf,gDSPACE(o(log(log(n))))=DSPACE(1)DSPACE(o(log⁡(log⁡(n))))=DSPACE(1)DSPACE(o(\log(\log(n)))) = DSPACE(1)
2
Najnowsze publikacje TCS z aspektami filozoficznymi
Wiele publikacji informatycznych z lat 50. i 60. XX wieku zawiera fascynujące spekulacje filozoficzne na temat natury umysłu i znaczenia informacji w odniesieniu do świata fizycznego. Słynne przykłady to „Test Turinga”, „Obliczanie przestrzeni” Zuse'a, „It from bit” Wheelera itp. Dziś takie tematy są szeroko omawiane w książkach popularnonaukowych, ale wydaje …
1
Klasy złożoności dla dowodów wiedzy
Pytanie zadane mi przez Grega Kuperberga. Zastanawiam się, czy są jakieś prace, które definiują i badają złożoność klas języków dopuszczających różnego rodzaju dowody wiedzy . Klasy takie jak SZK i NISZK są niezwykle naturalne z punktu widzenia złożoności, nawet jeśli całkowicie zapomnieliśmy o zerowej wiedzy i po prostu zdefiniowaliśmy je …
1
Odniesienie do algorytmu testowania acykliczności mieszanego grafu?
Wykres mieszany to wykres, który może mieć zarówno skierowane, jak i nieukierowane krawędzie. Podstawowy nieukierowany wykres jest uzyskiwany przez zapomnienie orientacji skierowanych krawędzi, a w drugim kierunku orientacja mieszanego wykresu jest uzyskiwana przez przypisanie kierunku każdej nieukierunkowanej krawędzi. Zestaw krawędzi tworzy cykl na wykresie mieszanym, jeśli można go zorientować w …
1
Czy DPDA bez ruchów
W formalnym opisie deterministycznych automatów wypychających pozwalają one na ruchy , w których maszyna może wyskakiwać lub pchać symbole na stos bez odczytywania symbolu z wejścia. Jeśli te ϵ ruchy są niedozwolone, a stos można zmodyfikować tylko raz po odczytaniu każdego symbolu, czy wynikowe automaty są równe mocy DPDA?ϵϵ\epsilonϵϵ\epsilon Może …
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.