NP-complete decision problems for binary quadratics
From MaRDI portal
Publication:1243130
DOI10.1016/0022-0000(78)90044-2zbMath0369.68030OpenAlexW2031206336WikidataQ56157366 ScholiaQ56157366MaRDI QIDQ1243130
Kenneth L. Manders, Leonard M. Adleman
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
A direct method for simulating partial recursive functions by Diophantine equations, A computational DNA solution approach for the quadratic Diophantine equation, An augmented filled function for global nonlinear integer optimization, A note on quadratic residuosity and UP, Seventeen lines and one-hundred-and-one points, Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets, Complexity of Subcases of Presburger Arithmetic, Division by zero, Short Presburger Arithmetic Is Hard, A transfer method from bounded existential Diophantine equations to Tarski algebra formulas, Decision Questions for Probabilistic Automata on Small Alphabets, Complexity yardsticks for \(f\)-vectors of polytopes and spheres, On the complexity of simple arithmetic expressions, A NEW QUANTUM ALGORITHM FOR SOLVING THE MINIMUM SEARCHING PROBLEM, Constraint Satisfaction Problems over Numeric Domains, On the number of integer points in translated and expanded polyhedra, \(\text{NP}\not={co}\)-NP and models of arithmetic, P, NP, Co-NP and weak systems of arithmetic, Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games, Diophantine complexity, Identification and signatures based on NP-hard problems of indefinite quadratic forms, The double exponential runtime is tight for 2-stage stochastic ILPs, The double exponential runtime is tight for 2-stage stochastic ILPs, Sentences over integral domains and their computational complexities, COMPLEXITY OF SHORT GENERATING FUNCTIONS, Mathematical problems for the next century, A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets, Unnamed Item, Combinatorial analysis (nonnegative matrices, algorithmic problems), Signatures Through Approximate Representations by Quadratic Forms
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
