Generalized Knapsack problems and fixed degree separations

DOI10.1016/0304-3975(96)00002-3zbMath0900.68212OpenAlexW2063725460MaRDI QIDQ1351965

Felipe Cucker, Michael Shub

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(96)00002-3

Mathematics Subject Classification ID

Related Items

Exotic quantifiers, complexity classes, and complete problems ⋮ Generalized finite automata over real and complex numbers ⋮ An alternative to Ben-Or's lower bound for the knapsack problem complexity

Cites Work

• Separation of complexity classes in Koiran's weak model
• Computing over the reals with addition and order
• Lower bounds for arithmetic networks
• Computing over the reals with addition and order: Higher complexity classes
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generalized Knapsack problems and fixed degree separations