Lower bound arguments with ``inaccessible'' numbers
type: Item
instance of: scholarly article
title: Lower bound arguments with ``inaccessible'' numbers
zbMATH Open document ID: 0652.68039
DOI: 10.1016/0022-0000(88)90032-3
author: Martin Dietzfelbinger
author: Wolfgang Maass
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4064470
zbMATH Keywords: parallel random access machines
zbMATH Keywords: Minimum perfect matching
zbMATH Keywords: Shortest path
zbMATH Keywords: Traveling salesperson
zbMATH Keywords: linear decision trees
zbMATH Keywords: Knapsack
MaRDI profile type: Publication
full work available at URL: 0022-0000(88)90032-3
OpenAlex ID: W1486395995
cites work: Q4773298
cites work: Q3751008
cites work: A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
cites work: On the complexity of computations under varying sets of primitives
cites work: Q3903002
cites work: On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
cites work: A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
cites work: Lower bounds for solving linear diophantine equations on random access machines
cites work: Q3940846
cites work: Simulation of Parallel Random Access Machines by Circuits
cites work: Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
cites work: Trade-Offs between Depth and Width in Parallel Computation
Recommended article: Q3751008
Recommended article: On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
Recommended article: Lower bounds for Z-numbers
Recommended article: Q3749045
Recommended article: Lower bounds for arithmetic problems
Recommended article: Numbers with Integer Complexity Close to the Lower Bound
Recommended article: Q5387684
Recommended article: Lower bounds for the numerical radius
Recommended article: Q4817889
description: scientific article; zbMATH DE number 4064470