From: Ray Vickson <rvickson@engmail.uwaterloo.ca>
Newsgroups: sci.math.symbolic
Subject: Re: integer solution
Date: Fri, 04 Dec 1998 11:22:23 -0500

Ronald Hui wrote:
> 
> Hi,
> 
> I am working on a problem, involving finding a POSITIVE INTEGER
> SOLUTION

Do you mean positive (i.e., strictly > 0), or do you mean non-negative?


> to the linear equations. I am appreciated if you can give me
> some help in this problem.
> 
>  I know that the software Maple V can solve my problem by the command
> isolve
> , using Hermitian normal form.  However, the function cannot be exported
> to C
> program. As a result, I plan to implement by myself.
> 
> Since the number of variables is larger than that of equations, I can
> always set some variables to be integers. But I don't know how to set
> them so that others are also integers.
> 
> Could you give me some suggestion of how to solve this problem?

The problem of the existence or non-existence of non-negative integer
solutions to a set of linear equations is NP-complete. This means that
in the worst case it will probably involve something like a potentially
explosive search tree. (The word "probably" refers to the fact that such
problems are not PROVABLY difficult; it's just that hundreds of smart
people working on them for decades have found no theoretically good
algorithms.) You might find it helpful to read some more about
NP-completeness. The classic, but somewhat dated reference is "Computers
and Intractability: a Guide to the Theory of NP-Completeness", M.R.
Garey and D.S. Johnson, Freeman, 1979.


> 
> Since I seldom check the newsgroup, I would prefer you email the answer
> to me.
>             cchui6@ie.cuhk.edu.hk
> 
> Thank you very much for your attention.
> 
> Ronald