On space-efficient algorithms for certain NP-complete problems (Q1314378)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On space-efficient algorithms for certain NP-complete problems |
scientific article |
Statements
On space-efficient algorithms for certain NP-complete problems (English)
0 references
1 March 1995
0 references
In \textit{J. Vyskoč} [ibid. 51, 221-227 (1987; Zbl 0642.68072)] existence of a class of algorithms solving certain NP-complete problems in \(O (n^{1g k}2^{n/2})\) time and \(O(k2^{n/k})\) space was claimed. Later, the claim was shown to be invalid by \textit{M. Cosnard}, \textit{J. Duprat} and \textit{A. G. Ferreira} [ibid. 67, 115-120 (1989; Zbl 0678.68034)], and another algorithm supposedly having the same time and space bounds has been presented in \textit{J. Vyskoč} [ibid. 70, No. 2, 273-274 (1990; Zbl 0701.68034)]. The article reviewed ends the sequence by showing that the approach advocated in Vyskoč's articles cannot yield to algorithms having simultaneously such time and space bounds.
0 references
space complexity
0 references
NP-complete problems
0 references
searching
0 references
0 references