Browse Prior Art Database

NF'-Complete Number-Theoretic Problem

IP.com Disclosure Number: IPCOM000128541D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 25 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Eitan M. Gurari: AUTHOR [+4]

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...