ON SPACE-EFFICIENT ALGORITHMS FOR CERTAIN NP-COMPLETE PROBLEMS

Authors
FERREIRA A
Citation
A. Ferreira, ON SPACE-EFFICIENT ALGORITHMS FOR CERTAIN NP-COMPLETE PROBLEMS, Theoretical computer science, 120(2), 1993, pp. 311-315
Citations number
6
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
120
Issue
2
Year of publication
1993
Pages
311 - 315
Database
ISI
SICI code
0304-3975(1993)120:2<311:OSAFCN>2.0.ZU;2-2
Abstract
Some recent results claimed the existence of a class of algorithms for certain NP-complete problems, with running time O(n(lg k) 2n/2) and s torage requirements 0(k 2n/k), for 2 less-than-or-equal-to k less-than -or-equal-to n. In this note we show that those results do not hold, i mplying that an algorithm with time 0(n 2n/2) and space 0(2n/4) is sti ll the best-known solution for such class of NP-complete problems.