On space-efficient algorithms for certain NP-complete problems (Q1314378): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Merging and Sorting Applied to the Zero-One Knapsack Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of selection in \(X+Y\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of searching in \(X+Y\) and other multisets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An \(O(n^{lg\,k}\cdot 2^{n/2})\) time and \(O(k\cdot 2^{n/k})\) space algorithm for certain NP-complete problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Corrigendum: An \(O(n^{lg\,k}\cdot 2^{n/2})\) time and \(O(k\cdot s^{n/k})\) space algorithm for certain NP-complete problems / rank | |||
Normal rank |
Latest revision as of 13:04, 22 May 2024
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