Startseite > Publikationen > 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

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.

hni1926.pdf

## Bibtex

@article{hniid=1926,
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
{"ft_lang_label":"__label__en","ft_lang_prob":0.61911374,"math_prob":0.9281156,"size":1860,"snap":"2019-43-2019-47","text_gpt3_token_len":491,"char_repetition_ratio":0.10021552,"word_repetition_ratio":0.23655914,"special_character_ratio":0.26344085,"punctuation_ratio":0.1536232,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98712015,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-20T23:30:08Z\",\"WARC-Record-ID\":\"<urn:uuid:b6267569-42a9-4fa6-8759-8c55b267fbc1>\",\"Content-Length\":\"15866\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ccbf0232-45da-430c-b87e-4e3ab192957d>\",\"WARC-Concurrent-To\":\"<urn:uuid:49b9508f-b4e7-4748-8252-5ff3cbb510c9>\",\"WARC-IP-Address\":\"131.234.137.122\",\"WARC-Target-URI\":\"https://www.hni.uni-paderborn.de/publikationen/publikationen/?tx_hnippview_pi1%5Bpublikation%5D=1926\",\"WARC-Payload-Digest\":\"sha1:QLU5I2GELZACSMEQMZ6A6KKU56JFA6E3\",\"WARC-Block-Digest\":\"sha1:45FMU7LRW67XF7RLJY7TPEUSQBUCFXTU\",\"WARC-Identified-Payload-Type\":\"application/xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496670635.48_warc_CC-MAIN-20191120213017-20191121001017-00366.warc.gz\"}"}