Суцествует ли полиномиальный по времени алгоритм над множеством вещественных чисел, который определяет возможность решения линейной системы неравенств $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].