From: Ray Vickson
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