Bandwidth constraints on problems complete for polynomial time (Q791316): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(83)90078-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2053805167 / rank | |||
Normal rank |
Revision as of 23:20, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bandwidth constraints on problems complete for polynomial time |
scientific article |
Statements
Bandwidth constraints on problems complete for polynomial time (English)
0 references
1983
0 references
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.
0 references
path system problem
0 references
bandwidth constraints
0 references
time-space alternating classes
0 references