On a complexity hierarchy between L and NL

DOI10.1016/0020-0190(88)90057-9MaRDI QIDQ1114402zbMATH OpenOpenAlexFDO

Authors Sang Cho, Dung T. Huynh

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90057-9

zbMATH Keywords

complexity class of languagesone-way nondeterministic counter machineunary knapsack

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Review text

This paper attempts to explain the complexity of the unary 0-1 knapsack problem which lies between L and NL. We introduce a new complexity class of languages log-space reducible to languages accepted by the family of one-way one-turn nondeterministic auxiliary counter machines whose auxiliary worktapes are O(\(\sqrt{\log n})\) bounded. This complexity class is denoted by \(LOG(1-1-NAuxCM(\sqrt{\log n})).\) We show that the modified unary knapsack problem with bandwidth \(2^{O(\sqrt{\log n})}\) is log- space complete for \(LOG(1-1-NAuxCM(\sqrt{\log n})).\) By varying the space bound on the auxiliary worktape, we obtain a hierarchy of complexity classes between L and NL.

Recommendations

• Knapsack problems for NL
• scientific article; zbMATH DE number 512811
• Space hierarchy theorem revised.
• scientific article; zbMATH DE number 1848283
• On the Structure of Logspace Probabilistic Complexity Classes

Cites work

• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• A taxonomy of problems with fast parallel algorithms
• Finite-Turn Pushdown Automata
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(8)

• A note on the space complexity of some decision problems for finite automata
• On the computational complexity of problems related to distinguishability sets
• On the complexity of the Leibniz hierarchy
• On partially blind multihead finite automata.
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• On languages accepted with simultaneous complexity bounds and their ranking problem
• Knapsack problems for NL
• On the universe, disjointness, and containment problems for simple machines

This page was built for publication: On a complexity hierarchy between L and NL

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114402)