P, NP, AND THE POST CORRESPONDENCE PROBLEM

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.