Uniform normal form for general time-bounded complexity classes

摘要

Refining techniques of previous works, we obtain a normal form arithmetical representation for non-deterministic computability, in which the polynomial matrix does not involve the time-bounding function. This permits arithmetization of Turing machine complexity classes determined by quite general time bounds. Applications are made to complexity hierarchies and to obtain a single, uniform, normal form.