Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

1
Znalezienie gwiazdy 5-punktowej w czasie wielomianowym
Chcę ustalić, że jest to część mojej pracy domowej na kursie, który obecnie biorę. Szukam pomocy w postępowaniu, NIE ODPOWIEDZI. Oto pytanie: Gwiazda pięcioramienna na niekierowanym wykresie jest pięcioklasową. Pokaż, że 5-POINTED-STAR , gdzie 5-POINTED-STAR = zawiera gwiazdę 5-punktową jako podgraf .∈P∈P\in P{<G>{<G>\{ :G:G: G}}\} Gdzie klika to CLIQUE = …
1
Przybliżenie minimalnej przepustowości drzew binarnych
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji przepustowości. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978 . …
1
Złożoność obliczeniowa a hierarchia Chomsky'ego
Zastanawiam się ogólnie nad związkiem między złożonością obliczeniową a hierarchią Chomsky'ego. W szczególności, jeśli wiem, że jakiś problem jest NP-zupełny, czy wynika z tego, że język tego problemu nie jest pozbawiony kontekstu? Na przykład problem kliki jest NP-zupełny. Czy wynika z tego, że język odpowiadający modelom z klikami ma pewną …
1
Maszyny o dostępie swobodnym z tylko dodawaniem, mnożeniem, równością
Literatura jest dość jasna, że ​​jednostronne pamięci RAM z pierwotnym mnożeniem są nieuzasadnione, ponieważ są nie mogą być symulowane przez maszyny Turinga w czasie wielomianowym potrafi rozwiązać problemy związane z PSPACE w czasie wielomianowym Jednak wszystkie odniesienia, które mogę znaleźć na ten temat (Simon 1974, Schonhage 1979) obejmują również operacje …
1
Znalezienie optymalnej sekwencji pytań w celu zminimalizowania całkowitego czasu studenta
Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .kkkQ={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k \}nnnS={s1…sn}S={s1…sn}S = \{ s_1 \ldots …
1
Czy ustalenie, czy istnieje liczba pierwsza w przedziale, o którym wiadomo, że jest w P czy NP-zupełna?
Widziałem z tego postu przy przepełnieniu stosu, że istnieją pewne stosunkowo szybkie algorytmy przesiewania przedziału liczb, aby sprawdzić, czy jest liczba pierwsza w tym przedziale. Czy to jednak oznacza, że ​​ogólny problem decyzyjny: (Czy istnieje liczba pierwsza w przedziale?) Znajduje się w P. (Było wiele odpowiedzi na ten post, których …
3
Teoretyczna złożoność trudna do sprawdzenia wartości
Funkcja zliczania liczb pierwszych , zdegradowana , jest zdefiniowana jako liczba liczb pierwszych mniejsza lub równa x .π(x)π(x)\pi(x)xxx Możemy zdefiniować problem decyzyjny z w następujący sposób:π(x)π(x)\pi(x) Biorąc pod uwagę dwie liczby i n , zapisane binarnie, zdecyduj, czy π ( x ) = n .xxxnnnπ(x)=nπ(x)=n\pi(x) = n Rozmawiałem dziś z …
4
Czy problem izomorfizmu grafu został rozwiązany?
Wydaje się, że strona problemu z izomorfizmem grafu w Wikipedii wskazuje, że nie, nie została rozwiązana. Jednak mój przyjaciel zwrócił uwagę na algorytm wielomianu czasowego dla izomorfizmu grafowego . Nie jestem wystarczająco wyrafinowany, aby podążać za rozumowaniem zawartym w artykule. Mam własną bardzo trudną próbę zastosowania algorytmu wielomianowego bez żadnego …
2
Czy krzyżówki wyrażeń regularnych są trudne NP?
Pewnego dnia wygłupiałem się na tej stronie: http://regexcrossword.com/ i zastanawiałem się, jaki był najlepszy sposób rozwiązania tego problemu. Czy potrafisz rozwiązać następujący problem w czasie wielomianowym, czy jest to trudne NP? Biorąc pod uwagę siatkę NxM z N wyrażeniami regularnymi dla kolumn i M dla wierszy, znajdź dowolne rozwiązanie siatki, …
2
analiza czasu algorytmu „wielkość wejściowa” a „elementy wejściowe”
Nadal jestem trochę mylony z terminami „długość wejściowa” i „rozmiar wejściowy”, gdy są używane do analizy i opisu bezobjawowej górnej granicy algorytmu Wydaje się, że długość wejściowa dla algorytmu zależy od rodzaju danych i algorytmu, o którym mówisz. Niektórzy autorzy odnoszą się do długości wejściowej do rozmiaru znaków, które są …
1
Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP
Załóżmy, że .P≠NPP≠NPP\neq NP Co możemy powiedzieć o granicach czasu działania wszystkich problemów związanych z NP-zupełnością? tj. jakie są najostrzejsze funkcje dla których możemy zagwarantować, że optymalny algorytm dla dowolnego problemu z NP zakończony będzie w czasie co najmniej i co najwyżej na wejściu o długości ? ω ( L …
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.