Generalized Knapsack problems and fixed degree separations

DOI10.1016/0304-3975(96)00002-3MaRDI QIDQ1351965zbMATH OpenOpenAlexFDO

Authors 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

Cites work

• scientific article; zbMATH DE number 3917710 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Computing over the reals with addition and order
• Computing over the reals with addition and order: Higher complexity classes
• Lower bounds for arithmetic networks
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Separation of complexity classes in Koiran's weak model

Cited in

(3)

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

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

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