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...
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...
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...
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...
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...
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...
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...
W „Obliczeniach kwantowych i informacjach kwantowych” Mike'a i Ike'a algorytm Grovera został szczegółowo wyjaśniony. Jednak w książce i we wszystkich wyjaśnieniach, które znalazłem w Internecie dla algorytmu Grovera, wydaje się, że nie ma wzmianki o tym, jak zbudowana jest Wyrocznia Grovera, chyba...
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”...
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...
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,...
Czy istnieją interesujące przypadki algorytmów, które zostały opublikowane ze sprawdzonymi granicami i gdzie opublikowano później ściśle lepsze ograniczenia? Nie lepsze algorytmy z lepszymi granicami - oczywiście tak się stało! Ale lepsza analiza prowadząca do lepszego powiązania z istniejącym...
Jaka jest następująca odmiana na okładce zestawu jako? Biorąc pod uwagę zbiór S, zbiór C podzbiorów S i dodatnią liczbę całkowitą K, czy istnieją zestawy K w C, tak że każda para elementów S leży w jednym z wybranych podzbiorów. Uwaga: Nietrudno dostrzec, że ten problem jest NP-Complete: Biorąc...
To pytanie dotyczy algorytmu Fishera-Yatesa służącego do zwracania losowego losowania danej tablicy. The Wikipedii mówi, że jego złożoność wynosi O (n), ale myślę, że jest to O (n log n). W każdej iteracji i losowa liczba całkowita jest wybierana między 1 a i. Po prostu zapisywanie liczby...
Szukam algorytmu online, aby utrzymać przechodnie przechodzenie ukierunkowanego wykresu acyklicznego o złożoności czasowej mniejszej niż O (N ^ 2) na dodanie krawędzi. Mój obecny algorytm wygląda następująco: For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in...
Biorąc pod uwagę język L zdefiniowany przez maszynę Turinga, która go decyduje, czy możliwe jest algorytmiczne określenie, czy L leży w
Mówi się, że problem P występuje w APX, jeśli istnieje pewna stała c> 0, tak że istnieje algorytm aproksymacji czasu wielomianowego dla P ze współczynnikiem aproksymacji 1 + c. APX zawiera PTAS (widoczne po prostu przez wybranie dowolnej stałej c> 0) i P. Czy APX jest w NP? W szczególności,...
Jestem studentem informatyki i obecnie planuję projekt dyplomowy. Potrzebuję pomysłów w dziedzinie obliczeń kwantowych. jakaś
Czy istnieją teraz prostsze algorytmy / dowody do triangulacji płaskiego wielokąta w czasie liniowym? Co jest dobrym źródłem wiedzy na temat najnowszego znanego
W tym artykule Erika D. Demaine'a, Sandora P. Fekete, Roberta J. Langa na stronie 15, ryc. 13, „Opakowanie w koło do projektowania origami jest trudne”, twierdzą, że długość boku najmniejszego kwadratu obejmującego dwa koła każdy z obszaru 1/2 wynosi 1,471299. Z moich obliczeń wynika, że długość...