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.)

4
Zliczanie liczby osłon wierzchołków: kiedy jest to trudne?
Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu G=(V,E)G=(V,E)G = (V, E) . Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).GGGd=|E||V|d=|E||V|d = \frac{|E|}{|V|} Mam wrażenie, że problem powinien być łatwiejszy zarówno wtedy, gdy jest rzadki, jak …
3
Przykłady problemów, w których algorytmy wykładnicze działają szybciej niż algorytmy wielomianowe dla praktycznych rozmiarów?
Czy znasz jakieś problemy (najlepiej przynajmniej nieco dobrze znane), w których dla praktycznego rozmiaru problemu algorytm wykładniczy działa znacznie szybciej niż najbardziej znany odpowiednik czasu wielomianowego. Załóżmy na przykład, że problem ma praktyczny rozmiar * i istnieją dwa znane algorytmy: jeden to a drugi to dla pewnej stałej . Oczywiście …
1
Rozróżnianie dwóch monet
Powszechnie wiadomo, że złożoność odróżnianie się stronniczy monetę z jednego sprawiedliwego jest θ ( ε - 2 ) . Czy istnieją wyniki dla odróżnienia monety p od monety p + ϵ ? Widzę, że dla specjalnego przypadku p = 0 złożoność będzie wynosić ϵ - 1 . Mam przeczucie, że …
2
Eliminacja gaussowska pod względem działania grupowego
Eliminacja Gaussa sprawia, że ​​wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że ​​obliczenia są trwałe, tj. Trudniejszy niż problemy ). Prowadzi to do pewnego rodzaju symetrii w wyznaczniku, np. …
1
Czy twierdzenie Kannana implikuje, że NEXPTIME ^ NP ⊄ P / poly?
Czytałem artykuł Buhrmana i Homera „Obwody wielobiegunowe, Prawie rzadkie wyrocznie i hierarchia wykładnicza” . Na dole strony 2 zauważają, że wyniki sugerują, że nie ma obwodów wielomianowych. Wiem, że w wykładniczej hierarchii czasu to po prostu , a także wiem, że wynikiem jest to, że tak, że . Oczywiście twierdzenie …
1
Optymalne solwery NP
Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć testy czy jest to poprawna”. Jest optymalna w tym sensie, że biorąc pod uwagę …
5
Czy istnieją rozstrzygalne problemy, dla których w przypadku braku algorytmu nie możemy ustalić granic czasowych?
Czy istnieją rozstrzygalne problemy, takie że dla żadnego algorytmu, który nie rozwiązałby problemu, możemy wyznaczyć limit czasowy jako funkcję długości n instancji wejściowej? Doszedłem do tego pytania, ponieważ myślałem o następujących kwestiach: Załóżmy, że mamy rekurencyjnie wymienny, ale nierozstrzygalny problem. Załóżmy dalej, że jestem przyczyną problemu „tak”. Następnie, dla żadnego …
2
Złożoność testowania członkostwa dla skończonych grup abelowych
Rozważ następujący problem testowania członkostwa w podgrupie abelian . Wejścia: Skończona grupa abelowa G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} o dowolnie dużych didid_i . Wytwarzające osadzone {h1,…,hn}{h1,…,hn}\lbrace h_1,\ldots,h_n\rbrace podgrupy H⊂GH⊂GH\subset G . Element b∈Gb∈Gb\in G . Wyjście: „tak”, jeżeli b∈Hb∈Hb\in H i „nie” w innym miejscu. Pytanie: Czy ten problem można skutecznie rozwiązać na klasycznym …
2
Odwracanie listy przy użyciu dwóch kolejek
To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N …
1
Czy
Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .D …
3
Czy możemy obliczyć
Szukam wydajnego algorytmu dla problemu: Wejście : dodatnia liczba całkowita 3)n3n3^n (zapisana w bitach) dla jakiejś liczby całkowitej n ≥ 0n≥0n \geq 0 . Wyjście : liczba nnn . Pytanie : Czy możemy obliczyć nnn na podstawie bitów 3)n3)n3^n w czasie O ( n )O(n)O(n) ? To jest teoretyczne pytanie …
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.