An NP-complete number-theoretic problem

DOI10.1145/800133.804349MaRDI QIDQ5402559zbMATH OpenOpenAlexWikidataFDO

Authors Eitan M. Gurari, Oscar H. Ibarra

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800133.804349

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25) Applications of computability and recursion theory (03D80) Higher degree equations; Fermat's equation (11D41) Decidability (number-theoretic aspects) (11U05) Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30)

Cited in

(7)

• The complexity of the equivalence problem for two characterizations of Presburger sets
• On selective unboundedness of VASS
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• scientific article; zbMATH DE number 1262805 (Why is no real title available?)
• scientific article; zbMATH DE number 958366 (Why is no real title available?)
• SPLITTING NUMBER is NP-complete
• On the complexity of convex and reverse convex prequadratic constraints

This page was built for publication: An NP-complete number-theoretic problem

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