Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space

Yuri Gurevich, Saharon Shelah

Browse the full STOC paper archive.