Lower bounds for linear satisfiability problems

We prove an Omega(n(inverted right perpendicularr/2inverted left perpendicu lar)) lower bound for the following problem: For some fixed linear equation in r variables, given n real numbers, do any r of them satisfy the equatio n? Our lower bound holds in a restricted linear decision tree model, in whi ch each decision is based on the sign of an arbitrary linear combination of r or fewer inputs. In this model, our lower bound is as large as possible. Previously, this lower bound was known only for a few special cases and on ly in more specialized models of computation. Our lower bound follows from an adversary argument. We show that for any al gorithm, there is a input that contains Omega(n(inverted right perpendicula rr/2inverted left perpendicular)) "critical" r-tuples, which have the follo wing important property. None of the critical tuples satisfies the equation ; however, if the algorithm does not directly test each critical tuple, the n the adversary can modify the input, in a way that is undetectable to the algorithm, so that some untested tuple does satisfy the equation. A key ste p in the proof is the introduction of formal infinitesimals into the advers ary input. A theorem of Tarski implies that if we can construct a single in put containing infinitesimals that is hard for every algorithm, then for ev ery decision tree algorithm there exists a corresponding real-valued input which is hard for that algorithm.