文章基本信息

标题：Bounds for Linear Satisfiability Problems
本地全文：下载
作者：Jeff Erickson
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：1999
卷号：1999
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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.