Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Суцествует ли полиномиальный по времени алгоритм над множеством вещественных чисел, который определяет возможность решения линейной системы неравенств $A x \geqslant b$ ?
Требуемый этой задачей алгоритм является алгоритмом, заданным машиной вещественных чисел в смысле, указанном в [5] (см. также проблему 3). Система имеет в качестве входных данных вещественную матрицу $A$ размерностью $m \times n$ и вектор $b \in \mathbb{R}^{m}$. В задаче требуется определить, существует ли некоторое $x \in \mathbb{R}^{n}$, для которого $\sum_{j=1}^{n} a_{i j} x_{j} \geqslant b_{i}$ при всех $i=1, \ldots, m$. Затрачиваемое измеряется количеством арифметических операций. Эта задача приведена в [5].
Один из вариантов решения этой задачи связан с ее рассмотрением как задачи оптимизации линейного программирования. При заданных выше $A, b$ и $c \in \mathbb{R}^{n}$ следует решить, существует ли
\[
\max _{x \in \mathbb{R}^{n}} c \cdot x \quad \text { при условии } A x \geqslant b,
\]
и если существует, то результатом вычислений является полученный вектор $x$.
Известный симплекс-метод Данцига представляет алгоритм для решения обеих задач (над $\mathbb{R}$ ), однако Кли и Минти доказали, что в наихудшем случае он является экспоненциально медленным. С другой стороны, мы с Боргвардтом и с последующей значительной поддержкой Хаймовича доказали, что в среднем время вычислений этого алгоритма полиномиально. Все это описано в [51].
Существует еще один метод на основе модели Тьюринга, с использованием рациональных чисел $\mathbb{Q}$ и затрат на вычисления, измеряемых «битами». Основываясь на идеях Юдина-Немировского, Хачин нашел полиномиальный по времени алгоритм (метод эллипсоидов) для задачи линейного программирования. Впоследствии Кармаркар с помощью своего «метода внутренней точки» нашел практический алгоритм решения этой задачи, для которого в рамках модели Тьюринга он доказал полиномиальность по времени. Все сказанное выше описано в [20], а также [51].
Близко к основной описанной выше проблеме над $\mathbb{R}$ лежит подобная задача, требующая найти «строго полиномиальный алгоритм» над $\mathbb{Q}$ для решения рассмотренных задач линейного программирования. При этом требуется, чтобы количество арифметических операций, а также количество бит-операций полиномиально зависело от битовой величины входных данных. Частичные результаты по этой проблеме были получены Мегидо и Тардо см. [20]. Описание задачи над $\mathbb{R}$ см. также в [3] и [68].
