Startseite > Publikationen > Publikationen


Meyer auf der Heide, Friedhelm:

Fast algorithms for N-dimensional restrictions of hard problems..

J. ACM 35(3): S. 740-747, Jul. 1988


Abstract. Let M be a parallel RAM with p processors and arithmetic operations addition and subtraction recognizing L subset of N^n in T steps. (Inputs for M are given integer by integer, not bit by bit.) Then L can be recognized by a (sequential!) linear search algorithm (LSA) in O(n^(4)(log(n) + T + log(p))) steps. Thus many n-dimensional restrictions of NP-complete problems (binary programming, traveling salesman problem, etc.) and even that of the uniquely optimum traveling salesman problem, which is Δ{from 2 to p)-complete, can be solved in polynomial time by an LSA. This result generalizes the construction of a polynomial LSA for the n-dimensional restriction of the knapsack problem previously shown by the author, and destroys the hope of proving nonpolynomial lower bounds on LSAs for any problem that can be recognized by a PRAM as above with 2^(poly(n)) rocessors in poly(n) time.




author = {Meyer auf der Heide, Friedhelm},
title = {Fast algorithms for N-dimensional restrictions of hard problems.},
journal = {J. ACM},
volume = {35(3)},
pages = {740-747},
month = jul,
year = {1988},

BibTeX in die Zwischenablage kopieren