Lower bound arguments with ``inaccessible'' numbers (Q1107308)

The first result presented in this paper is a lower bound of \(\Omega\) (log n) for the computation time of concurrent-write parallel random access machines (PRAMs) with operation set \(\{+\), -, multiplication by constants\(\}\) that recognize the ``threshold set'' \(\{\) \(\bar x\in {\mathbb{Z}}^ n |\) \(x_ 1+...+x_{n-1}\leq x_ n\}\) for inputs from \(\{\) 0, 1, 2,..., \(2^{O(n-\log n)}\}^ n\). The same bound holds for PRAMs with arbitrary binary operations, if the size of the input numbers is not restricted. The second lower bound regards languages in \({\mathbb{R}}^ n\) corresponding to `Knapsack', `Minimum perfect matching', `Shortest path', and `Traveling salesperson' on linear decision trees (LDTs) with the restriction that the number of negative coefficients \(\alpha_ i\) in each test \(\sum_{1\leq i\leq n}\alpha_ ix_ i:\) \(\alpha_ 0\) is bounded by f(n). The lower bounds on the depth of such LDTs that recognize these languages are \(\Omega (2^{\lfloor n/2f(n)\rfloor})\) for `Knapsack' and \(\Omega (2^{\lfloor \sqrt{n}/4f(n)\rfloor})\) for the graph problems. The common new tool in the proofs of these lower bounds is the method of constructing ``hard'' instances \((x_ 1,...,x_ n)\) of the respective problem by building up the input numbers \(x_ i\) from ``mutually inaccessible'' numbers, i.e., numbers of different orders of magnitude. [See also the review of the prelimincomputing; lower bound; leader finding on rings of processors. We prove a lower bound of \(nH_ n\approx 0.346n \log n\) for the average number of messages for distributed leader finding in asynchronous, bidirectional rings of processors.