Startseite > Publikationen > Publikationen

Publikationen

Meyer auf der Heide, Friedhelm:

Lower Bounds for Solving Linear Diophantine Equations on Random Access Machines.

J. ACM 32(4): S. 929-937, Jul. 1985

Abstract

The problem of recognizing the language L_n(L_{n,k}) of solvable Diophantine linear equations with n variables (and solutions from {0,...,k}^n) is considered. The languages |U_n elem N L_n, U_n elem N L_{n,1}, the knapsack problem, are NP-complete. The Omega(n^2) lower bound for L_{n,1} on linear search algorithms due to Dobkin and Lipton is generalized to an Omega(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 Omega(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 Omega(r^2 log(k + 1)) lower bound is obtained for RAMS recognizing L_n or L_{n,k}, for inputs from {0, ... ,(nk)^{O(n^2)}}^n.

Dateien

hni1947.pdf



Bibtex

@article{hniid=1947,
author = {Meyer auf der Heide, Friedhelm},
title = {Lower Bounds for Solving Linear Diophantine Equations on Random Access Machines},
journal = {J. ACM},
volume = {32(4)},
pages = {929-937},
month = jul,
year = {1985},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1947