Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space

DOI10.1145/79147.214070zbMath0699.68063OpenAlexW2015314424MaRDI QIDQ3477959

Publication date: 1990

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/79147.214070

zbMATH Keywords

counting lower bounds graph algorithms structures cliques nondeterminism problems combinatorial algorithms complexity measures complexity classes trade-offs bounded-action devices computation by abstract devices computations on discrete

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (4)

Graph properties checkable in linear time in the number of vertices ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Time-space tradeoffs for satisfiability ⋮ Lower bounds on the complexity of recognizing SAT by Turing machines

This page was built for publication: Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space