### Fast algorithms for $\textit{N}-dimensional$ restrictions of hard problemsFast algorithms for $\textit{N}-dimensional$ restrictions of hard problems

Access Restriction
Subscribed

 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

Source: ACM Digital Library