Pytania otagowane jako time-complexity

Złożoność czasowa problemów decyzyjnych lub relacji między klasami złożoności czasowej. (Użyj znacznika [analiza-algorytmów] dla czasu wymaganego przez poszczególne algorytmy.)

3
Równoważne sformułowanie teorii złożoności w rachunku Lambda?
W teorii złożoności definicja złożoności czasu i przestrzeni odnosi się do uniwersalnej maszyny Turinga: odpowiednio. liczba kroków przed zatrzymaniem i liczba dotkniętych komórek na taśmie. Biorąc pod uwagę tezę Kościoła-Turinga, powinno być możliwe zdefiniowanie złożoności również pod względem rachunku lambda. Moje intuicyjne założenie jest takie, że złożoność czasu może być …
1
Porównywanie dwóch produktów z list liczb całkowitych?
Załóżmy, że mam dwie listy liczb całkowitych dodatnich o ograniczonej męskości i biorę iloczyn wszystkich elementów każdej listy. Jaki jest najlepszy sposób ustalenia, który produkt jest większy? Oczywiście mogę po prostu obliczyć każdy produkt, ale mam nadzieję, że istnieje bardziej wydajne podejście, ponieważ liczba cyfr w produktach wzrośnie liniowo wraz …
0
Prosta ścieżka na sztyfcie z tylnymi krawędziami
Jaka jest złożoność następującego problemu ( P? NP-trudny?):∈∈\in Dane wejściowe: ukierunkowany wykres acykliczny , zestaw tylnych krawędzi E ′ ⊂ V × V i dwa odrębne węzły sD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsss i .ttt Pytanie: Niech oznacza wykres utworzony przez dodanie do D krawędzi od E ′ . Czy istnieje prosta ścieżka …
2
Co się stanie, jeśli poprawimy twierdzenia dotyczące hierarchii czasu?
f,gf,gf,gf(n)logf(n)=o(g(n))f(n)log⁡f(n)=o(g(n))f(n) \log f(n) = o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )DTIME(f(n))⊊DTIME(g(n))DTIME(f(n))⊊DTIME(g(n)) DTIME(f(n)) \subsetneq DTIME(g(n))f,gf,gf,gf(n+1)=o(g(n))f(n+1)=o(g(n))f(n+1)=o(g(n))jest to NTIME(f(n))⊊NTIME(g(n)).NTIME(f(n))⊊NTIME(g(n)). NTIME(f(n)) \subsetneq NTIME(g(n)). Istnieje wiele (starych i aktualnych) wyników, które wykorzystują twierdzenia o hierarchii czasu do udowodnienia dolnych granic. Oto moje pytania: Co się …
1
Ukryte stałe w złożoności algorytmów
W przypadku wielu problemów algorytm o największej złożoności asymptotycznej ma bardzo duży stały współczynnik, który jest ukryty przez dużą notację O. Dzieje się tak w przypadku mnożenia macierzy, mnożenia liczb całkowitych (w szczególności najnowszego algorytmu mnożenia liczb całkowitych O (n log n) Harveya i van der Hoevena), sieci sortowania o …
1
2-NEXPTIME-zupełne problemy
Mamy problem i znaleźliśmy algorytm, który wydaje się być 2-sekundowy. Chciałbym znaleźć znane problemy z niepełnym czasem 2, aby znaleźć dolną granicę. W literaturze znalazłem głównie dwa takie problemy: czy PCP jako rozwiązanie o rozmiarze mniejszym niż 2)2)n2)2)n2^{2^n} i problem uprawy roli dla kwadratu wielkości 2)2)n2)2)n2^{2^n} Jednak nie byłem w …
1
Algorytm przecięcia DFA dla szczególnych przypadków
Interesują mnie wydajne algorytmy przecięcia DFA w szczególnych przypadkach. Mianowicie, gdy DFA przecinają się, zachowują określoną strukturę i / lub działają na ograniczonym alfabecie. Czy jest jakieś źródło, w którym mogę znaleźć algorytmy takich przypadków? Aby pytanie nie było zbyt szerokie, szczególnie interesująca jest następująca struktura: wszystkie przecinające się DFA …
1
Czy możemy uzyskać posortowaną listę z posortowanej macierzy w
Jestem zmieszany. Chcę udowodnić, że problem sortowania macierzy przez , tj. Wiersze i kolumny są w porządku rosnącym, to . Kontynuuję, zakładając, że można to zrobić szybciej niż i próbuję złamać dolną granicę Dla porównań potrzebnych do posortowania m elementów. Mam dwie sprzeczne odpowiedzi:nnnnnnΩ (n2)logn )Ω(n2)log⁡n)\Omega(n^2\log n)n2)lognn2)log⁡nn^2\log nlog( m ! …
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.