Untergrenzen für lineares Erfüllbarkeitsproblem

10

In SODA 1995 zeigte Jeff Erickson Untergrenzen für die lineare Erfüllbarkeit (Überprüfung, ob eine Teilmenge von reellen Zahlen eine lineare Gleichung für Variablen erfüllt ). Die Beweismethode verwendet Infinitesimale und das Übertragungsprinzip von Tarski .n rrnr

Könnte jemand die Intuition hinter dem Weg erklären, der genommen wurde, um diese Bindung zu beweisen? Was ist die Schwierigkeit, einen direkten Beweis wie diesen zu finden: "Angesichts eines Entscheidungsbaums, der reelle Zahlen verwendet, können wir hier einen kontroversen Input konstruieren"?

Jagadisch
quelle
1
Ich gehe
MRA
1
entsprechend bearbeitet
Suresh Venkat
Ja, das ist das Papier, auf das ich mich beziehe. @suresh danke
Jagadish

Antworten:

2

In der Tat besteht das Hauptargument darin , einen Entscheidungsbaum zu erstellen und kontroverse Eingaben zu entwerfen, aber es gibt technische Probleme dabei, die die Infinitesimale vermeiden. Schauen Sie sich die Diskussion am Ende der ersten Spalte von Seite 2 an und fahren Sie fort, was dies ziemlich klar erklärt.

Suresh Venkat
quelle