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 .
¿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"?
Respuestas:
Yo fuertemente sugiero leer el más reciente documento de seguimiento por Ailon y Chazelle , lo que evita todo el tema infinitesimal en su totalidad. Si desea seguir con mi trabajo, lea la versión del diario ( Chicago J Theoretical Computer Science 1999 ). La versión SODA tiene un error importante en la Sección 5, y (creo) que la versión del diario explica la prueba principal con mucha más claridad.
fuente
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.
fuente