Lower bounds for solving linear diophantine equations on random access machines

Publisher Website
Google Scholar
Abstract
The problem of recognizing the language L n ( L n, k ) of solvable Diophantine linear equations with n variables (and solutions from {O, … , k } n ) is considered. The languages ∪ nϵN L n , ∪ nϵN L n, l , the knapsack problem, are NP-complete. The Ω( n 2 lower bound for L n ,1 on linear search algorithms due to Dobkin and Lipton is generalized to an Ω( n 2 log( k + 1)) lower bound for L n, k . The method of Klein and Meyer auf der Heide is further improved to carry over the Ω( n 2 ) lower bound for L n,1 to random access machines (RAMS) in such a way that it holds for a large class of problems and for very small input sets. By this method, lower bounds that depend on the input size, as is necessary for L n , are proved. Thereby, an Ω( n 2 log( k + 1)) lower bound is obtained for RAMS recognizing L n or L n, k , for inputs from {0, … , ( nk ) 0 ( n 2 ) } n .

This publication has 2 references indexed in Scilit: