Задний план Вычисление по действительным числам более сложное, чем вычисление по натуральным числам, поскольку действительные числа являются бесконечными объектами и существует неисчислимо много реальных чисел, поэтому действительные числа не могут быть достоверно представлены конечными строками...
Задача суммы квадратных корней задает для заданных двух последовательностей a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n и b1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n натуральных чисел, является ли сумма ∑iai−−√∑iai\sum_i \sqrt{a_i} меньше, равно или больше суммы . Статус сложности этой проблемы открыт;...
Одним из основных принципов разработки алгоритма является нахождение сильно полиномиального алгоритма для линейного программирования, т. Е. Алгоритма, время выполнения которого ограничено полиномом по числу переменных и ограничений и не зависит от размера представления параметров (при условии...
Это может быть основной вопрос, но я читал и пытался понять статьи по таким темам, как вычисление равновесия по Нэшу и тестирование линейного вырождения, и не был уверен в том, как действительные числа указываются в качестве входных данных. Например, когда утверждается, что LDT имеет определенные...
Предположим, нам дано несколько непересекающихся простых многоугольников на плоскости и две точки и t вне каждого многоугольника. Задача евклидова кратчайшего пути состоит в том, чтобы вычислить евклидов кратчайший путь от s до t , который не пересекает внутреннюю часть любого многоугольника. Для...
В настоящее время вычисление действительных значений в большинстве популярных языков все еще выполняется с помощью операций с плавающей запятой. С другой стороны, теории, такие как эффективность второго типа (TTE) и теория предметной области, давно обещали точное вычисление действительных чисел....
Какова сложность (в стандартном целочисленном ОЗУ) вычисления стандартного дискретного преобразования Фурье вектора из nNn целых чисел? Классический алгоритм для быстрых преобразований Фурье , неуместно [1] приписываемый Кули и Тьюки, обычно описывается как выполняющийся за O(nlogn)О(NжурналN)O(n...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
В недавнем вопросе обсуждался теперь классический алгоритм динамического программирования для TSP, независимо от Беллмана и Хельда-Карпа . Алгоритм повсеместно сообщается работать в O(2nn2)O(2nn2)O(2^n n^2) времени. Однако, как недавно заметил один из моих учеников, это время выполнения может...
Существует ли общая теорема, которая при надлежащей дезинфекции утверждает, что наиболее известные результаты, касающиеся использования действительных чисел, могут фактически использоваться при рассмотрении только вычислимых вещественных чисел? Или существует правильная характеристика результатов,...
Недавно я изучаю модель вычисления BSS (см., Например, Сложность и Реальные вычисления; Блум, Кукер, Шуб, Смейл.) Для вещественных чисел показано, что для заданной системы полиномов f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] существование нулей является N P R -полным. Однако мне интересно, если эти f...
В этой лекционной заметке Олы Свенссон: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf говорится, что мы не знаем, находится ли евклидова TSP в NP: Причина в том, что мы не знаем, как эффективно рассчитать квадратные корни. С другой стороны, есть документ Пападимитриу:...
Как мы знаем, определение вычислительной сложности алгоритма практически не вызывает противоречий, но определение вычислительной сложности вещественных чисел или моделей вычислений над действительными значениями не в таком случае. Мы знаем модель и модель Блюма и Смалеса в книге «Вычислительный...
Может ли кто-нибудь указать мне на ссылку на неопределяемость модуля функционала непрерывности в PCF? \newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Андрей Бауэр написал очень хороший пост в блоге, в котором более подробно рассматриваются некоторые вопросы, но я кратко изложу его...
Используя модель real-RAM / BSS, мы имеем класс NP (где BSS - это модель компьютера Блума-Шуб-Смейла с операциями над реалами). У нас есть NP полные проблемы. Итак, вопрос в том, существует ли аналог гипотезы Бермана Хартманиса для класса NP ? Конечно, поставленный здесь вопрос зависит от модели -...