Bandwidth constraints on problems complete for polynomial time (Q791316): Difference between revisions

The admissibility of a path system problem is considered. It is shown that its monotone version with a bandwidth f is log-space complete for the class of languages recognizable within polynomial-time and space f. Basing on this result it is ascertained that the class of sets accepted within polynomial-time and simultaneously polylog space coincides with the class of sets reducible by log-space transformations to sets accepted by one-way log log-space bounded alternating Turing machines. An inclusion for the alternating class \(ASPACE(f)\subset \cup_{k>0}DSPACE(2^{kf})\) is proved where the function \(f(n)=g(\log \log n)\) satisfies the following condition: for every integer m there exists \(c>0\) such that for almost all n an inequality \(g(n+m)\leq cg(n)\) is valid.