Knapsack problems for NL

DOI10.1016/0020-0190(95)00017-7zbMath1022.68559OpenAlexW2071108434MaRDI QIDQ673615

Birgit Jenner

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00017-7

zbMATH Keywords

computational complexitycombinatorial problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Knapsack in graph groups ⋮ Remarks on 0-1 Optimization Problems with Superincreasing and Superdecreasing Objective Functions ⋮ On partially blind multihead finite automata. ⋮ COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA ⋮ Unnamed Item ⋮ On Computational Power of Partially Blind Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a complexity hierarchy between L and NL
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• The iterated mod problem
• Symmetric space-bounded computation
• On tape-bounded complexity classes and multihead finite automata
• Space-bounded reducibility among combinatorial problems
• A taxonomy of problems with fast parallel algorithms
• New problems complete for nondeterministic log space
• `` Strong NP-Completeness Results

This page was built for publication: Knapsack problems for NL