This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines that use less than
logarithmic space - may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ... more >>>

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>