Chicago Journal of Theoretical Computer Science

Volume 1999

Article 8

Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe.

Bounds for Linear Satisfiability Problems

Jeff Erickson (University of Illinois, Urbana-Champaign)
6 August 1999

We prove an OMEGA(n^(ceiling(r/2))) 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 equation? Our lower bound holds in a restricted linear decision tree model, in which 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 only in more specialized models of computation.

Our lower bound follows from an adversary argument. We show that for any algorithm, there is a input that contains OMEGA(n^(ceiling(r/2))) ``critical'' r-tuples, which have the following important property. None of the critical tuples satisfies the equation; however, if the algorithm does not directly test each critical tuple, then 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 step in the proof is the introduction of formal infinitesimals into the adversary input. A theorem of Tarski implies that if we can construct a single input containing infinitesimals that is hard for every algorithm, then for every decision tree algorithm there exists a corresponding real-valued input which is hard for that algorithm.

DOI: 10.4086/cjtcs.1999.008
[] Article 7 [] Article 9
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Sat Mar 20 09:32:31 CST 1999