Нижние оценки для линейной задачи выполнимости

10

В SODA 1995 года Джефф Эриксон показал нижние оценки линейной выполнимости (проверяя, удовлетворяет ли некоторое подмножество действительных чисел линейному уравнению на переменных). Метод доказательства использует бесконечно малые и принцип переноса Тарского .н рrnr

Может ли кто-нибудь объяснить интуицию, лежащую за маршрутом, чтобы доказать эту связь? В чем сложность такого прямого доказательства: «Учитывая дерево решений, которое принимает действительные числа, вот как мы можем построить состязательный ввод»?

Jagadish
источник
1
Я полагаю, вы ссылаетесь на этот документ: portal.acm.org/citation.cfm?id=313772
MRA,
1
отредактировано соответственно
Суреш Венкат
Да, это бумага, на которую я ссылаюсь. @suresh спасибо
Джагадиш

Ответы:

15

Я настоятельно рекомендую прочитать более позднюю статью Аилона и Шазель , в которой полностью исключается бесконечно малый вопрос. Если вы хотите придерживаться моей статьи, пожалуйста, прочитайте версию журнала ( Chicago J теоретическая информатика 1999 ). В версии SODA есть серьезная ошибка в Разделе 5, и (я думаю) версия журнала объясняет основное доказательство гораздо более четко.

Jeffε
источник
2

Действительно, главный аргумент является чтобы построить дерево решений и спроектировать состязательный ввод, но при этом существуют технические проблемы, которых избегают бесконечно малые. Посмотрите на обсуждение внизу первого столбца страницы 2 и продолжайте, что объясняет это довольно ясно.

Суреш Венкат
источник