Límites inferiores para problemas de satisfacción lineal

10

En SODA 1995 , Jeff Erickson mostró límites más bajos para la satisfacción lineal (verificando si algún subconjunto de n números reales satisface una ecuación lineal en las variables r ). El método de prueba utiliza infinitesimales y el principio de transferencia de Tarski .rnr

¿Alguien podría explicar la intuición detrás de la ruta tomada para probar este límite? ¿Cuál es la dificultad para llegar a una prueba directa como esta: "Dado un árbol de decisión que toma números reales, así es como podemos construir una entrada de confrontación"?

Jagadish
fuente
1
Supongo que se refiere a este documento: portal.acm.org/citation.cfm?id=313772
MRA
1
editado adecuadamente
Suresh Venkat
Sí, ese es el papel al que me refiero. @suresh gracias
Jagadish

Respuestas:

2

De hecho, el argumento principal es construir un árbol de decisión y diseñar una entrada contradictoria, pero hay problemas técnicos al hacer esto que los infinitesimales evitan. Mire la discusión en la parte inferior de la primera columna de la página 2 y continúe, lo que explica esto con bastante claridad.

Suresh Venkat
fuente