An NP-Complete Number-Theoretic Problem
From MaRDI portal
Publication:4194462
DOI10.1145/322139.322152zbMath0407.68053OpenAlexW2088191001MaRDI QIDQ4194462
Oscar H. Ibarra, Eitan M. Gurari
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322139.322152
Diophantine EquationNp-CompleteCounter MachineNonlinear Integer ProgrammingPolynomial Time-Bounded Turing MachineUndecidability of Hilbert's Tenth Problem
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Simple counter machines and number-theoretic problems ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ The complexity of almost linear diophantine problems ⋮ Some classes of languages in \(NC^ 1\) ⋮ Counter machines and verification problems.
This page was built for publication: An NP-Complete Number-Theoretic Problem
