NP-complete decision problems for binary quadratics
From MaRDI portal
Publication:1243130
DOI10.1016/0022-0000(78)90044-2zbMath0369.68030WikidataQ56157366 ScholiaQ56157366MaRDI QIDQ1243130
Leonard M. Adleman, Kenneth L. Manders
Publication date: 1978
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(78)90044-2
Related Items
\(\text{NP}\not={co}\)-NP and models of arithmetic, P, NP, Co-NP and weak systems of arithmetic, A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets, A note on quadratic residuosity and UP, Combinatorial analysis (nonnegative matrices, algorithmic problems), On the complexity of simple arithmetic expressions, Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games, Sentences over integral domains and their computational complexities, A direct method for simulating partial recursive functions by Diophantine equations, Mathematical problems for the next century, Seventeen lines and one-hundred-and-one points, Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets, Diophantine complexity, Complexity of Subcases of Presburger Arithmetic, A NEW QUANTUM ALGORITHM FOR SOLVING THE MINIMUM SEARCHING PROBLEM, Identification and signatures based on NP-hard problems of indefinite quadratic forms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Riemann's hypothesis and tests for primality
- Every Prime Has a Succinct Certificate
- Reduction of an arbitrary diophantine equation to one in 13 unknowns
- Contributions to the theory of diophantine equations I. On the representation of integers by binary forms