Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-028 | 17th April 2000 00:00

Time-Space Tradeoffs for Nondeterministic Computation

RSS-Feed




TR00-028
Authors: Lance Fortnow, Dieter van Melkebeek
Publication: 23rd May 2000 16:18
Downloads: 3456
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint