On space-efficient algorithms for certain NP-complete problems (Q1314378): Difference between revisions

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.