Limites inferiores para problemas de satisfação linear

10

Na SODA 1995 , Jeff Erickson mostrou limites mais baixos para a satisfação linear (verificando se um subconjunto de de números reais satisfaz uma equação linear nas variáveis ). O método de prova usa infinitesimais e o princípio de transferência de Tarski .rrnr

Alguém poderia explicar a intuição por trás do caminho percorrido para provar isso? Qual é a dificuldade em apresentar uma prova direta como esta: "Dada uma árvore de decisão que leva números reais, eis como podemos construir uma entrada contraditória"?

Jagadish
fonte
11
Suponho que você se refira a este documento: portal.acm.org/citation.cfm?id=313772
MRA
11
editado adequadamente
Suresh Venkat
Sim, é a esse artigo que estou me referindo. @suresh thanks
Jagadish

Respostas:

2

De fato, o principal argumento é construir uma árvore de decisão e projetar informações contraditórias, mas há problemas técnicos com isso que os infinitesimais evitam. Observe a discussão na parte inferior da primeira coluna da página 2 e continue, o que explica isso com bastante clareza.

Suresh Venkat
fonte