On a complexity hierarchy between L and NL (Q1114402)

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.