Bandwidth constraints on problems complete for polynomial time
type: Item
instance of: scholarly article
title: Bandwidth constraints on problems complete for polynomial time
zbMATH Open document ID: 0535.68021
DOI: 10.1016/0304-3975(83)90078-6
author: I. H. Sudborough
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3850473
zbMATH Keywords: path system problem
zbMATH Keywords: bandwidth constraints
zbMATH Keywords: time-space alternating classes
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90078-6
OpenAlex ID: W2053805167
cites work: Lower bounds on space complexity for contextfree recognition
cites work: An algorithm for reducing the bandwidth of a matrix of symmetrical configuration
cites work: Q5674871
cites work: On Relating Time and Space to Size and Depth
cites work: Alternation
cites work: Minimizing the bandwidth of sparse symmetric matrices
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: An observation on time-storage trade off
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Q3944008
cites work: Space bounds for processing contentless inputs
cites work: Complexity Results for Bandwidth Minimization
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q5592246
cites work: Space-bounded reducibility among combinatorial problems
cites work: Q4192112
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Relations Among Complexity Measures
cites work: Tree-size bounded alternation
cites work: On uniform circuit complexity
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Q4142695
cites work: An extension of Savitch's theorem to small space bounds
Wikidata QID: Q127662435
description: scientific article; zbMATH DE number 3850473