# NF'-Complete Number-Theoretic Problem

Original Publication Date: 1977-Dec-31

Included in the Prior Art Database: 2005-Sep-16

## Publishing Venue

Software Patent Institute

## Related People

Eitan M. Gurari: AUTHOR [+3]

## Abstract

We look at systems of non-linear equations of the form [Equation ommitted] where A is a m x n matrix of rational constants and [Equation ommitted] are column vectors. Each [Equation ommitted] where ri(x) is a rational function of x with rational coefficients. We show that the problem of deciding for a given system D whether there exists a non-negative integral solution (yl,...,yn,x) satisfying D and finding one such solution, if it exists, is solvable. In fact, the same problem restricted to systems satisfying a certain condition on "encoding" is DIP-complete. Without the restriction the problem has exponential time complexity. Key Words and Phrases: NP-complete, number-theoretic problem, Diophantine equation, solvability, non-linear integer programming problem, polynomial time-bounded Turing machine CR categories: 5.23, 5.25, 5.26, 5.27, 5.41 * This research was partially supported by the National Science Foundation under Grant No. DCR75-17090.

**This text was extracted from a PDF file.**

**This is the abbreviated version, containing approximately 14% of the total text.**

__Page 1 of 25__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**NF'-Complete Number-Theoretic Problem* **

by

Eitan M. Gurari and Oscar H. Ibarra

0400312 Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 A Technical Report 77-12 August 1977

Cover design courtesy of Ruth and Jay Leavitt

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

**Abstract **

We look at systems of non-linear equations of the form

(Equation Omitted)

where A is a m x n matrix of rational constants and

(Equation Omitted)

are column vectors. Each

(Equation Omitted)

where ri(x) is a rational function of x with rational coefficients. We show that the problem of deciding for a given system D whether there exists a non-negative integral solution (yl,...,yn,x) satisfying D and finding one such solution, if it exists, is solvable. In fact, the same problem restricted to systems satisfying a certain condition on "encoding" is DIP-complete. Without the restriction the problem has exponential time complexity.

Key Words and Phrases: NP-complete, number-theoretic problem, Diophantine equation, solvability, non-linear integer programming problem, polynomial time-bounded Turing machine

CR categories: 5.23, 5.25, 5.26, 5.27, 5.41 * This research was partially supported by the National Science Foundation under Grant No. DCR75-17090.

**Introduction **

In [5] simple number-theoretic problems were shown NP-complete. (See 11,4,91 for motivations and other examples of NP-complete problems.) In particular, the problem of accepting the set of binary encodings of Diophantine equations of the form

University of Minnesota Page 1 Dec 31, 1977

__Page 2 of 25__NF'-Complete Number-Theoretic Problem

(Equation Omitted)

(a,b,c non-negative integers) which have non-negative integral solutions is NP-complete. The result is interesting since this problem, which we shall call T, is one of the simplest number- theoretic problems which have been shown NP-complete. The equation is clearly solvable in nondeterministic polynomial time since any solution (y,x) must satisfy

(Equation Omitted)

The determin-istic polynomial-time reduction of an NP-complete problem (the satisfi-ability problem was the one used in [5]) to problem T is the difficult part of the NP-completeness proof. In this paper, we shall consider another number-theoretic problem which includes T as a special case. The problem, which we shall refer to as F., is that of finding non-negative integral solutions to systems of non-linear equations of a special form. Thus FX is a non-linear integer programming problem. It is well known, of course, that the general non-linear integer programming problem is unsolvable, even if the equations contain only linear and quadratic constraints [3]. The proof is a direct application of the unsolvability of Hilbert's tenth problem [6]. (Hilbert's tenth problem is the problem of deciding...