  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.
