Lower bound arguments with “Inaccessible” numbers

摘要

The first result presented in this paper is a lower bound of Ω(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” tx̄ϵZn|x1+…+ xn-̊1⩽xn∼ for inputs from 0, 1, 2,…, 2O(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 Rn 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 ai in each test Σ1⩽i⩽nαixi: α0 is bounded by f(n). The lower bounds on the depth of such LDTs that recognize these languages are Ω(2⌊2f(n)⌋) for KNAPSACK and Ω(2⌊√n4f(n)⌋) for the graph problems. The common new tool in the proofs of these lower bounds is the method of constructing “hard” instances (x1, …, xn) of the respective problem by building up the input numbers x1 from “mutually inaccessible” numbers, i.e., numbers of different orders of magnitude.