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

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

Cited in

(6)

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

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)