文章基本信息
- 标题：Time-Space Tradeoffs for Nondeterministic Computation
- 本地全文：下载
- 作者：Lance Fortnow ; Dieter van Melkebeek
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2000
- 卷号：2000
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
We show new tradeoffs for satisfiability and nondeterministic
linear time. Satisfiability cannot be solved on general purpose
random-access Turing machines in time n 1 618 and space
n o (1) . This improves recent results of Lipton and Viglas and
Fortnow. - 关键词：
satisfiability , time-space tradeoffs
