An NP-Complete Number-Theoretic Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An NP-Complete Number-Theoretic Problem

Full text

Pdf (825 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 3 (July 1979) table of contents

Pages: 567 - 581

Year of Publication: 1979

ISSN:0004-5411

Authors

Eitan M. Gurari	Department of Computer Science, University of Minnesota, Minneapolis, MN
Oscar H. Ibarra	Department of Computer Science, University of Minnesota, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 43, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322139.322152 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BOROSH, I, AND TREYBIG, L B Bounds on posmve integral solutions of hnear D,ophantme equauons Proc Amer Math Soc 55 (1976), 299-304
	2	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	3	DAVIS, M, MATIJASEVIC, Y, AND ROBINSON, J Hdbert's tenth problem Dtophantme equations Positive aspects of a negatwe soluuon Proc Symp Pure Mathematws 28 (1976), 323-378.
	4	GARFINKEL, R S, AND NEMHAUSER, G L Integer Programming, Wiley, New York, 1972
	5	GURARI, E, AND IBARRA, O H Two-way counter machines and Dlophantme equaUons. (In preparation )
	6	GURARI, E, AND {BARRA, O H A decidable class of counter machines with applications to some numbertheoreuc problems CSci Tech Rep No 77-10, U of Minnesota, Mlnneapohs, Mmn To appear m J Comptr and Syst Sct
	7	HILBERT, D Mathemausche Probleme Vortrag, gehalten auf dem internauonalen Mathematlker-Kongrass zu Parts 1900, Nachr Akad Wlss Gottmgen Math-Phys (1900), 253-297, Transl.. Bull Amer Math Soc 8 (1901-1902), 437-479
	8	Oscar H. Ibarra, Reversal-Bounded Multicounter Machines and Their Decision Problems, Journal of the ACM (JACM), v.25 n.1, p.116-133, Jan. 1978 [doi>10.1145/322047.322058]
	9	JEROSLOW, R G There cannot be any algorithm for integer programming with quadrauc constraints Oper Res 21 (1973), 221-224
	10	KARP, R M Reducibility among combinatorial problems In Complemty of Computer Computations, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-104
	11	LIU, L AND WEINER, P A characterlzatlon of semdlnear sets J Comptr and Syst Sct. 4 (1970). 299-307
	12	LUENBERGER, D G Introduction to Lmear and Nonhnear Programming Addison-Wesley, Reading, Mass, 1973
	13	Kenneth Manders , Leonard Adleman, NP-complete decision problems for quadratic polynomials, Proceedings of the eighth annual ACM symposium on Theory of computing, p.23-29, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803627]
	14	MATIJASEVI(~, Y Enumerable sets are Dlophantme (Russian) Dokl Akad Nauk SSSR 191 (1970), 279-282
	15	MATIJASEVI(~, Y, AND ROBINSON, J Reduction of an arbitrary Dlophantme equation to one m 13 unknowns Acta Arithmenca 27 (1975), 521-553
	16	SAHNI, S Computauonally related problems SIAM J Comptng 3 (1974), 262-279
	17	SIEGEL, C Zur theone de quadratischen formen Nachr A kad Wi~s Gottmgen Math,-Phys K1 II (1972), 21-46
	18	SKOLEM, T Dlophantische glelchungen Ergeblsse d Math u Ihrer Grenzgebwte Bd 5, Springer, 1938

CITED BY 3

	Oscar H. Ibarra , Jianwen Su , Zhe Dang , Tevfik Bultan , Richard A. Kemmerer, Counter machines and verification Problems, Theoretical Computer Science, v.289 n.1, p.165-189, 23 October 2002
	Eitan M. Gurari , Oscar H. Ibarra, Two-Way Counter Machines and Diophantine Equations, Journal of the ACM (JACM), v.29 n.3, p.863-873, July 1982
	Volker Weispfenning, Complexity and uniformity of elimination in Presburger arithmetic, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.48-53, July 21-23, 1997, Kihei, Maui, Hawaii, United States