Lower bounds for linear satisfiability problems
Lower bounds for linear satisfiability problems
复制标题
线性可满足性问题的下界
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Jeff Erickson
中科院分区：
文献类型：
--
作者：
Jeff Erickson
我们证明了以下问题的ω（NDR/2E）下限：对于R变量中的某些固定线性方程，给定n个实数，它们是否满足方程式？ ，其中每个决定是基于R或更少的输入的任意线性组合的符号。我们的较低限制是从广告参数中进行的，我们表明，对于任何算法，都有一个包含ω（NDR/2E）的“关键” R-tuples但是，关键的元组满足方程式；确实满足方程式。存在相应的实价输入，对于该算法来说很难。
We prove an Ω(ndr/2e) 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 Ω(ndr/2e) “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. An extended abstract of this paper can be found in [Eri95].