tło Obliczenia na liczbach rzeczywistych są bardziej skomplikowane niż obliczenia na liczbach naturalnych, ponieważ liczby rzeczywiste są obiektami nieskończonymi i istnieje niezliczona liczba liczb rzeczywistych, dlatego liczb rzeczywistych nie można wiernie przedstawić za pomocą ciągów...
Suma pierwiastki problemu prosi, ponieważ dwie sekwencje i dodatnich liczb całkowitych czy suma mniejszy, równy lub większy niż suma . Status złożoności tego problemu jest otwarty; zobacz ten post, aby uzyskać więcej informacji. Problem ten powstaje naturalnie w geometrii obliczeniowej, szczególnie...
Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu...
To może być podstawowe pytanie, ale czytałem i próbowałem zrozumieć artykuły na takie tematy, jak obliczenia równowagi Nasha i liniowe testy degeneracji, i nie byłem pewien, jak liczby rzeczywiste są określone jako dane wejściowe. Na przykład, kiedy stwierdzono, że LDT ma pewne dolne granice...
Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że...
Obecnie obliczanie liczb rzeczywistych w najpopularniejszych językach jest nadal wykonywane za pomocą operacji zmiennoprzecinkowych. Z drugiej strony, teorie takie jak efektywność typu drugiego (TTE) i teoria domen od dawna obiecują dokładne obliczenie rzeczywistych liczb. Najwyraźniej problem...
Jaka jest złożoność (na standardowej całkowitej liczbie pamięci RAM) obliczania standardowej dyskretnej transformaty Fouriera wektora nnn liczb całkowitych? Klasyczny algorytm szybkich transformacji Fouriera , niewłaściwie [1] przypisany Cooleyowi i Tukeyowi, jest zwykle opisywany jako działający...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Ostatnie pytanie dotyczyło teraz klasycznego algorytmu programowania dynamicznego dla TSP, niezależnie od Bellmana i Held-Karpa . Algorytm jest powszechnie zgłaszany do działania w czasie . Jednak, jak niedawno zauważył jeden z moich studentów, ten czas działania może wymagać nieracjonalnie silnego...
Czy istnieje ogólne twierdzenie, które przy odpowiedniej dezynfekcji stanowiłoby, że najbardziej znane wyniki dotyczące użycia liczb rzeczywistych mogą być rzeczywiście wykorzystane przy rozważaniu tylko liczb rzeczywistych? Czy też istnieje właściwa charakterystyka wyników, które pozostają...
Ostatnio studiuję model obliczeniowy BSS (por. Na przykład złożoność i obliczenia rzeczywiste; Blum, Cucker, Shub, Smale). Na Real , widoczne jest, że biorąc pod uwagę system wielomianu f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] Istnienie zer jest N P R -Complete. Zastanawiam się jednak, czy te f są...
W notatkach z wykładu Oli Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf mówi się, że nie wiemy, czy Euclidean TSP jest w NP: Powodem jest to, że nie wiemy, jak skutecznie obliczać pierwiastki kwadratowe. Z drugiej strony jest ten artykuł Papadimitriou:...
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w...
Czy ktoś może wskazać mi odniesienie do niezdefiniowalności modułu ciągłości funkcjonalnej w PCF? \ newcommand {\ bool} {\ mathsf {bool}}\newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer napisał bardzo fajny post na blogu , w którym szczegółowo omawia niektóre problemy,...
Korzystając z modelu rzeczywistej pamięci RAM / BSS, mamy klasę NP R (gdzie BSS to model Blum-Shub-Smale komputera z operacjami nad rzeczywistością). Mamy kompletne problemy z NP R. Pytanie zatem, czy istnieje analogia do hipotezy Bermana Hartmanisa dla klasy NP R ? Oczywiście postawione tutaj...