Formal Language Characterizations of P, NP, and PSPACE

Based on the notions of locality and recognizability for n-dimensional languages n-dimensionally colourable 1-dimensional languages are introduced. It is shown: A language L is in NP if and only if L is n-dimensionally colourable for some n. An analogous characterization in terms of deterministic n-dimensional colourability is obtained for P. The addition of one unbounded dimension for colouring leads to a characterization of PSPACE.