Существуют ли известные алгоритмы для следующей задачи, которые побеждают наивный алгоритм?
Вход: система из m линейных неравенств.
Вывод: выполнимое решение если оно существует.
Предположим, что и b имеют целочисленные записи. Меня интересуют границы в худшем случае.
источник