论文研究-保持空间复杂性的算法组合.pdf

【文件属性】：

文件名称：论文研究-保持空间复杂性的算法组合.pdf

文件大小：202KB

文件格式：PDF

更新时间：2022-08-11 11:54:08

算法组合,空间复杂性,库克归约,预言机查询

分析了组合两种算法所需的空间复杂度在何种情况下为原算法的空间复杂度之和的问题，即空间复杂度的保持问题。通过形式化oracle查询方式，证明了在后续oracle查询和前面所有的oracle回复都不相关，即非适应性查询情况下，算法组合将保持空间复杂性，但在适应性查询情况时不一定成立。