Access Restriction

Author Meyer auf der Heide, Friedhelm
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Let $\textit{M}$ be a parallel RAM with $\textit{p}$ processors and arithmetic operations addition and subtraction recognizing L ⊂ $N}\textit{n}$ in $\textit{T}$ steps. (Inputs for $\textit{M}$ are given integer by integer, not bit by bit.) Then $\textit{L}$ can be recognized by a (sequential) linear search algorithm (LSA) in $\textit{O}(\textit{n}4(log(\textit{n})$ + $\textit{T}$ + $log(\textit{p})))$ steps. Thus many $\textit{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 $Δ\textit{P}2-complete,$ can be solved in polynomial time by an LSA. This result generalizes the construction of a polynomial LSA for the $\textit{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 $2poly(\textit{n})$ processors in $poly(\textit{n})$ time.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 3
Page Count 8
Starting Page 740
Ending Page 747

Open content in new tab

   Open content in new tab
Source: ACM Digital Library