Pytania otagowane jako complexity-theory

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

6
Dlaczego nie istniał algorytm szyfrowania oparty na znanych problemach NP-Hard?
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 NP-trudnym. Brzmi (przynajmniej teoretycznie) tak, jakby był …
7
Czy ustawodawstwo NP jest kompletne?
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 gra karciana Magic: the Gathering jest zarówno NP, …
9
Jakie byłyby rzeczywiste implikacje konstruktywnego dowodu ?
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 dowód , jakie byłyby natychmiastowe skutki takiego odkrycia? P=NPP=NPP=NP Nie proszę o opinie na …
6
Dlaczego niektóre gry są kompletne?
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, co oznacza, …
3
Problem z plecakiem - NP-kompletny pomimo dynamicznego rozwiązania programistycznego?
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 prawdopodobnie niemożliwe. Gdzie jest mój błąd?
4
Dlaczego czas wielomianowy nazywany jest „wydajnym”?
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 jest wydajny. Gdzie jest logika ?!nlognnlog⁡nn^{\log n}n80n80n^{80} (a) …
4
Jakie są typowe techniki wzajemnego ograniczania problemów?
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 . Zasadniczo pokazujemy, że każdy …
7
Wyjaśnienie znaczenia asymptotycznej złożoności algorytmów w praktyce projektowania algorytmów
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 instancji. Algorytm, który działa dobrze w praktyce na skończonej liczbie instancji, którymi jesteśmy zainteresowani, …
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.