Próbuję rozwiązać konkretny problem i pomyślałem, że mogę go rozwiązać za pomocą teorii automatów. Zastanawiam się, jakie modele automatów mają rozstrzygające rozstrzyganie w czasie wielomianowym? tzn. jeśli masz maszyny M.1, M2)M.1,M.2)M_1, M_2 , możesz sprawdzić, czy wydajnie.L ( M1) ⊆ L (...
Czy następujący problem występuje w trybie PTIME lub coNP-hard: Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennyche1e1e_1e2e2e_2 , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań 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...
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że...
Biorąc pod uwagę macierz m×nm×nm \times n (przy założeniu, że m≥nm≥nm \ge n ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn? Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany...
Czy istnieje algorytm tasowania karabinu liniowego w czasie? Jest to algorytm, który niektóre szczególnie sprawne ręce są w stanie wykonać: równomierne dzielenie tablicy wejściowej o równej wielkości, a następnie przeplatanie elementów dwóch połówek. Mathworld ma krótką stronę na temat losowania...
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...
Szukam informacji o złożoności obliczeniowej mnożenia macierzy prostokątnych macierzy. Wikipedia stwierdza, że złożoność pomnożenia przez B ∈ R n × p wynosi O ( m n p ) (mnożenie podręcznika).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) Mam...
Stały czas jest absolutnie niskim stopniem złożoności czasu. Można się zastanawiać: czy jest coś nietypowego, co można obliczyć w stałym czasie? Jeśli trzymamy się modelu maszyny Turinga, niewiele można zrobić, ponieważ odpowiedź może zależeć tylko od początkowego odcinka wejścia o stałej długości,...
Przeszukałem to, ale i tak nie znalazłem odpowiedzi. Huck odpowiedział na to w pełni. Dzięki
Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe...
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 złożoność będzie zależeć od...
Mówimy, że funkcja jest konstruowalna w czasie , jeśli istnieje deterministyczna wielopasmowa maszyna Turinga M, która na wszystkich wejściach długości n wykonuje co najwyżej f ( n ) kroki i dla każdego n istnieje pewien wkład długość n, na której M wykonuje dokładnie f ( n ) kroki.fa: N →...
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,...
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...
To, co nazywam liczeniem, to problem polegający na znalezieniu liczby rozwiązań funkcji. Dokładniej, biorąc pod uwagę funkcję fa: N→ { 0 , 1 }f:N→{0,1}f:N\to \{0,1\} (niekoniecznie czarna skrzynka), przybliżone # { x ∈ N∣ f( x ) = 1 } = | fa- 1( 1 ) |#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}=...
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ć...
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...
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...
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...