Zacznę od zauważenia, że jest to problem związany z pracą domową, proszę podać tylko porady i związane z nimi obserwacje, proszę BEZ BEZPOŚREDNIEJ ODPOWIEDZI . Powiedziawszy to, oto problem, na który patrzę: Niech HALF-CLIQUE = { | jest nieukierowanym wykresem posiadającym pełny podsgraf z co...
Według Immermana klasa złożoności powiązana z zapytaniami SQL jest dokładnie klasą bezpiecznych zapytań w (zapytania pierwszego rzędu plus operator zliczania): SQL przechwytuje bezpieczne zapytania. (Innymi słowy, wszystkie zapytania SQL mają złożoność w , a wszystkie problemy w mogą być wyrażone...
Wpadłem w następujące wątpliwości co do złożoności Towers of Hanoi , co do których chciałbym waszych komentarzy. Czy to jest w NP? Próba odpowiedzi: Załóżmy, że Peggy (przysłowie) rozwiązuje problem i przekazuje go Victorowi (weryfikatorowi). Victor łatwo widzi, że końcowy stan rozwiązania jest...
W artykule Złożoność problemu Frobeniusa autorstwa Ramíreza-Alfonsína okazało się, że problemem jest NP-zupełność za pomocą redukcji Turinga. Czy to jest możliwe? Jak dokładnie? Myślałem, że było to możliwe tylko w przypadku wielomianowego wielokrotnego zmniejszenia. Czy są jakieś odniesienia na...
W książce Sipsera „Wprowadzenie do teorii obliczeń” na stronie 286 zmniejszono z 3SAT do problemu ścieżki Hamiltona. Czy istnieje prostsza redukcja? Mówiąc prościej, mam na myśli redukcję, która byłaby łatwiejsza do zrozumienia (dla studentów). Czy istnieje redukcja wykorzystująca liniową...
Szukam przykładów problemu, który ma dolną granicę ) dla wejścia .Ω(|x|2Ω(|x|2\Omega(|x|^2xxx Problem musi mieć następujące właściwości: Ω(n2)Ω(n2)\Omega(n^2) Środowisko wykonawcze dla dowolnego algorytmu - priorytetem jest możliwie najprostszy argument dolnej granicy. O(n2)O(n2)O(n^2)Algorytm ,...
Moim celem jest rozwiązanie następującego problemu, który opisałem na podstawie jego danych wejściowych i wyjściowych: Wejście: Kierunkowy wykres acykliczny z m węzłami, n źródłami i 1 ujściem ( m > n ≥ 1 ).GGGmmmnnn111m>n≥1m>n≥1m > n \geq 1 Wynik: VC wymiar (lub zbliżanie niego) dla...
Czy wymagane jest, aby problem trudny do przeprowadzenia w NP był obliczalny? Nie sądzę, ale nie jestem
W Hromkovič's Algorytmics for Hard Problems (2nd edition) znajduje się takie twierdzenie (2.3.3.3, strona 117): Istnieje (rozstrzygalny) problem decyzyjny taki że dla każdego algorytmu A, który rozwiązuje P, istnieje inny algorytm A ', który również rozwiązuje P i dodatkowo...
Czy dla każdej funkcji obliczalnej fff istnieje problem, który można najlepiej rozwiązać w czasie Θ(f(n))Θ(f(n))\Theta(f(n)) czy też istnieje funkcja obliczalna fff tak że każdy problem, który można rozwiązać w O(f(n))O(f(n))O(f(n)) może również być rozwiązany w czasie o(f(n))o(f(n))o(f(n)) ? To...
Badam złożoność obliczeniową i zastanawiałem się, dlaczego problemy z NP-Complete (NPC) są w ogóle ważną klasą. Wydaje mi się oczywiste, dlaczego chcemy pokazać, że dany problem NP jest trudny do przeprowadzenia. Rozumiem też definicję NPC, a pokazanie danego problemu decyzyjnego jest trudne dla...
W mnożeniu macierzy Strassena stwierdzamy jeden dziwny (przynajmniej dla mnie) fakt, że mnożenie macierzy dwóch 2 x 2 wymaga mnożenia 7. Pytanie: Jak udowodnić, że niemożliwe jest pomnożenie dwóch macierzy 2 x 2 w 6 pomnożeniach? Należy pamiętać, że macierze są ponad liczbami...
Podręczniki wszędzie założyć, że Bounded post Korespondencja Problem jest NP-zupełny (nie więcej niż NN.N indeksy dozwolony z powtórzeń). Nigdzie jednak nie pokazano prostej (jak w czymś, co student może zrozumieć) wielomianowej redukcji czasu z innego problemu pełnego NP. Jednak każda redukcja, o...
Wikipedia to określa Mówi się, że algorytm ma czas wielomianowy, jeśli jego czas działania jest ograniczony górną granicą przez wyrażenie wielomianowe wielkości wejściowej dla algorytmu, tj. dla pewnej stałej k.T.( n ) = O ( nk)T.(n)=O(nk)T(n) = O(n^k) Algorytm działa w silnie wielomianowym...
Dzięki twierdzeniu o maksymalnym przepływie min-cut wiemy, że możemy użyć dowolnego algorytmu do obliczenia maksymalnego przepływu na grafie sieciowym do obliczenia -min-cut. Dlatego złożoność obliczenia minimum -cięcie jest nie większa niż złożoność obliczenia przepływu maksymalnego .( s , t...
Jak wynika z mojego poprzedniego pytania , bawiłem się hipotezą Riemanna jako zagadnieniem matematyki rekreacyjnej. W trakcie tego procesu doszłam do dość interesującego nawrotu i jestem ciekawa jego nazwy, jej redukcji i podatności na rozwiązywanie luki między liczbami pierwszymi. Krótko mówiąc,...
Egzystencjalna teoria Real jest w PSPACE , ale nie wiem, czy to jest PSPACE zupełnych . Jeśli uważam, że tak nie jest, jak mogę to udowodnić? Mówiąc bardziej ogólnie, biorąc pod uwagę problem z pewną klasą złożoności X , jak mogę pokazać, że nie jest to X-Complete ? Na przykład X może oznaczać NP...
Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka...
I odczytu gdzieś, że najbardziej skuteczny algorytm znaleźć można obliczyć czynniki czasu, ale to kod pisał jest O ( n ) lub prawdopodobnie O ( n log n ) w zależności od tego, jak szybki jest podział i moduł. Jestem pewien, że coś gdzieś źle zrozumiałem, ale nie jestem pewien gdzie. Oto, co...
Czy istnieje jakaś ogólna technika dla udowodnienia, że problem NIE jest NP-Complete? Dostałem to pytanie na egzaminie, które poprosiło mnie o wykazanie, czy jakiś problem (patrz poniżej) jest NP-Complete. Nie mogłem wymyślić żadnego prawdziwego rozwiązania, a właśnie udowodniłem, że było w P....