COMPLEXITY MODELS FOR INCREMENTAL COMPUTATION

被引：51

作者：

MILTERSEN, PB

SUBRAMANIAN, S

VITTER, JS

TAMASSIA, R

机构：

[1] BROWN UNIV,DEPT COMP SCI,PROVIDENCE,RI 02912

[2] DUKE UNIV,DEPT COMP SCI,DURHAM,NC 27708

[3] BROWN UNIV,DEPT COMP SCI,PROVIDENCE,RI 02912

来源：

THEORETICAL COMPUTER SCIENCE | 1994年 / 130卷 / 01期

关键词：

Computation theory - Computational methods - Mathematical models - Theorem proving;

D O I：

10.1016/0304-3975(94)90159-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to existing complexity classes. We show that problems that have small sequential space complexity also have small incremental time complexity.

引用

页码：203 / 236

页数：34

共 24 条

[1]

BARRINGTON D, 1986, 18TH P ACM STOC, P1

[2]

BERMAN AM, 1990, ACTA INFORM, V27, P665, DOI 10.1007/BF00259471

[3]

Boppana R. B., 1990, HDB THEORETICAL COMP, VA, P757, DOI DOI 10.1016/B978-0-444-88071-0.50019-9]2

[4] PROBLEMS COMPLETE FOR DETERMINISTIC LOGARITHMIC SPACE [J].