Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes
<|reference_start|>Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes: Proving lower bounds remains the most difficult of tasks in computational complexity theory. In this paper, we show that whereas most natural NP-complete problems belong to NLIN (linear time on nondeterministic RAMs), some of them, typically the planar versions of many NP-complete problems are recognized by nondeterministic RAMs in linear time and sublinear space. The main results of this paper are the following: as the second author did for NLIN, we give exact logical characterizations of nondeterministic polynomial time-space complexity classes; we derive from them a class of problems, which are complete in these classes, and as a consequence of such a precise result and of some recent separation theorems using diagonalization, prove time-space lower bounds for these problems.<|reference_end|>
@article{chapdelaine2006lower,
    title={Lower bounds and complete problems in nondeterministic linear time and
  sublinear space complexity classes},
    author={Philippe Chapdelaine, Etienne Grandjean},
    journal={arXiv preprint arXiv:cs/0606058},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0606058},
    primaryClass={cs.CC cs.LO}
}