Pytania związane z (obliczeniową) złożonością rozwiązywania problemów
Większość współczesnego szyfrowania, takiego jak RSA, opiera się na faktoryzacji liczb całkowitych, co nie jest uważane za problem trudny dla NP, ale należy do BQP, co czyni go podatnym na komputery kwantowe. Zastanawiam się, dlaczego nie istniał algorytm szyfrowania oparty na znanym problemie...
Istnieje wiele prób udowodnienia albo albo P ≠ N P , i oczywiście wiele osób myśli o tym pytaniu, mając pomysły na udowodnienie obu kierunków.P = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Wiem, że istnieją metody, które okazały się nieskuteczne, i prawdopodobnie jest...
Zwykle w algorytmach nie dbamy o porównywanie, dodawanie lub odejmowanie liczb - zakładamy, że działają one w czasie O ( 1 )O(1)O(1) . Na przykład zakładamy, że mówimy, że sortowanie na podstawie porównania to O ( n logn )O(nlogn)O(n\log n) , ale gdy liczby są zbyt duże, aby zmieścić się w...
Chciałbym wiedzieć, czy były prace związane z kodeksem prawnym złożoności. W szczególności, przypuśćmy, że mamy problem decyzyjny „Czy biorąc pod uwagę tę książkę prawniczą i ten szczególny zestaw okoliczności, pozwany jest winny?” Do jakiej klasy złożoności należy? Są wyniki, które dowiodły, że...
Wydaje mi się, że mam rozsądne pojęcie o złożoności takiej jak , Θ ( n ) i Θ ( n 2 ) .O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) Jeśli chodzi o listę, to ciągłe wyszukiwanie, więc po prostu dostaje się na czele listy. Θ ( n ) , gdzie będę chodzić całą listę, a Θ ( n 2 ) idzie...
Rozumiem na wysokim poziomie problem i rozumiem, że gdyby absolutnie „udowodniono”, że jest to prawdą w dostarczonym rozwiązaniu, otworzyłoby to drzwi do rozwiązania wielu problemów w dziedzinie informatyki.P=NPP=NPP=NP Moje pytanie brzmi: jeśli ktoś opublikowałby niepodważalny, konstruktywny...
Czy istnieją problemy NP-zupełne, które dowiodły algorytmów podwykładniczych? Proszę o ogólne informacje na temat spraw, nie mówię tutaj o przypadkach specjalnych, które można zastosować. Pod wykładniczo rozumiem porządek wzrostu powyżej wielomianów, ale mniejszy niż wykładniczy, na przykład...
Dlaczego w informatyce jakakolwiek złożoność, która jest co najwyżej wielomianowa, jest uważana za wydajną? Dla każdego praktycznego zastosowania (a) algorytmy o złożoności są znacznie szybsze niż algorytmy działające w czasie, powiedzmy n 80 , ale pierwszy jest uważany za nieefektywny, a drugi...
Problemy z plecakiem można łatwo rozwiązać za pomocą programowania dynamicznego. Programowanie dynamiczne przebiega w czasie wielomianowym; dlatego to robimy, prawda? Przeczytałem, że jest to w rzeczywistości problem NP-zupełny, co oznaczałoby, że rozwiązanie problemu wielomianowego jest...
Przeczytałem wpis w Wikipedii na temat „ Listy problemów z NP-complete ” i odkryłem, że gry takie jak Super Mario, Pokemon, Tetris lub Saga Crush Candy są na przykład kompletne. Jak mogę sobie wyobrazić np. Kompletność gry? Odpowiedzi nie muszą być zbyt precyzyjne. Chcę tylko uzyskać przegląd tego,...
W algorytmach i złożoności skupiamy się na asymptotycznej złożoności algorytmów, tj. Ilości zasobów wykorzystywanych przez algorytm przy wielkości wejściowej do nieskończoności. W praktyce potrzebny jest algorytm, który działałby szybko w skończonej (choć prawdopodobnie bardzo dużej) liczbie...
W teorii obliczalności i złożoności (i być może w innych dziedzinach) redukcje są wszechobecne. Istnieje wiele rodzajów, ale zasada pozostaje ta sama: pokaż, że jeden problem jest co najmniej tak samo trudny jak jakiś inny problem poprzez odwzorowanie instancji z na równoważne z rozwiązaniem w ....
Wygląda na to, że na tej stronie ludzie często korygują innych za mylące „algorytmy” i „problemy”. Jakie są między nimi różnice? Skąd mam wiedzieć, kiedy powinienem rozważać algorytmy i problemy? A jak odnoszą się one do pojęcia języka w formalnej teorii
Programowanie liniowe (LP) jest w P, a programowanie liczb całkowitych (IP) jest trudne dla NP. Ponieważ jednak komputery mogą manipulować liczbami z ograniczoną precyzją, w praktyce komputer używa liczb całkowitych do programowania liniowego. Z tego powodu, czy LP i IP nie powinny należeć do tej...
Mój kolega i ja właśnie uderzyliśmy w notatki jednego z naszych profesorów. Notatki stwierdzają, że istnieją zadania, które można rozwiązać w czasie wielomianowym (są w klasie PF), ale NIE są możliwe do zweryfikowania w czasie wielomianowym (NIE są w klasie NPF). Aby rozwinąć te klasy: Otrzymujemy...
Czy są jakieś znane problemy w (a nie w ), które nie są ukończone? Rozumiem, że nie ma obecnie znanych problemów, ale nie zostało to wykluczone. NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP} Jeśli występuje problem, który to (a nie ), ale nie , czy byłby to wynik braku istniejącego izomorfizmu między...
Jest koszy i rodzajów piłek. th bin ma etykiet na , jest to oczekiwana liczba kulek typu .nnnmmmiiiai,jai,ja_{i,j}1≤j≤m1≤j≤m1\leq j\leq mjjj Zaczynasz od kul typu . Każda kula typu ma masę i chce umieścić kulki w pojemnikach tak, aby bin miał masę . Rozmieszczenie kulek, które utrzymują poprzednie...
Tak więc problem decyzyjny TSP (problem sprzedawcy podróży) jest NP kompletny . Ale nie rozumiem, w jaki sposób mogę sprawdzić, czy dane rozwiązanie TSP jest w rzeczywistości optymalne w czasie wielomianowym, biorąc pod uwagę, że nie ma sposobu na znalezienie optymalnego rozwiązania w czasie...
Zastanawiam się, czy istnieje dobry przykład łatwego do zrozumienia problemu NP-Hard, który nie jest NP-Complete i nie jest nierozstrzygalny? Na przykład problem zatrzymania jest NP-trudny, a nie NP-kompletny, ale jest nierozstrzygalny. Uważam, że oznacza to, że problem można zweryfikować, ale...
Istnieje prosty algorytm wielomianowy, który decyduje, czy istnieje ścieżka między dwoma węzłami na ukierunkowanym wykresie (po prostu wykonaj rutynowe przemierzanie wykresu za pomocą, powiedzmy, głębokości pierwszego wyszukiwania). Jednak wydaje się, że, co zaskakujące, problem staje się znacznie...