We define a variant of the Post Correspondence Problem, the machine-or
iented Post Correspondence Problem or MOPCP, especially suitable for c
omplexity considerations. All recursively enumerable sets can be repre
sented in terms of instances of MOPCP and, moreover, deterministic and
nondeterministic time and space complexities have their natural count
erpart in the representation. This leads to PCP-related complexity cla
sses; for instance, the time complexity classes PCP-P and PCP-NP. Usin
g a bounded delay injectivity condition on one of the morphisms of a P
CP instance, we obtain an exact characterization of P. In this charact
erization, determinism corresponds exactly to the bounded delay condit
ion and no reference is made to computations of any sort, A weaker bou
nded delay requirement gives rise to an infinite (possibly collapsing)
hierarchy between P and NP. (C) 1995 Academic Press, Inc.