1
$\begingroup$

Given

$$ a_1 X_1 + \dots + a_n X_n = b $$

where $a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time.

Also, what I really want is to do the above, but under the minimization of:

$$ X_1 + \dots + X_n, \ X_i \in \Bbb{N} $$

All my $X_i$ are bounded with small sets such as $\{0, 2\}$ for small input instances of my certain problem, however I can't very well try $2^n$ or more possibilities, now can I! That would not be polynomial time.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Could you make it easier for others to help you? Please add an accessible url to your "certain problem". $\endgroup$
    – John L.
    Aug 1, 2019 at 16:01
  • $\begingroup$ @Apass.Jack that will not work. I tried it in numerous posts on MSE. The fact is no one has interest in the problem I'm working on. So I present the abstraction only, which clearly has applications in many problems (see "integer programming"). Keeps the post elegant and simple enough to understand. It's really annoying that I cannot find any accessible research on the web for this long solved constraint problem. I don't care about the $n = 2$ case, I can write the formula from memory. I am interested in only the general case. Apparently most writers plaigiarize since 99% content is n=2! $\endgroup$
    – Daniel Donnelly
    Aug 1, 2019 at 16:13
  • $\begingroup$ @Apass.Jack adding in background, applications, certain problem (in this instance) will result in a wall-of-text that no one will read, bring up more questions than can be answered, and like I said, I've tried that over 50 times on MSE. The only way you're going to find out what problem I'm working on is if you deduce it from my MSE question history. This whole add in what certain problem you're working on each and every time is for the birds... I have proved to myself, through years of posting, that it makes no difference (at least on this problem), and is a complete waste of time. Nothx! $\endgroup$
    – Daniel Donnelly
    Aug 1, 2019 at 16:19
  • 1
    $\begingroup$ The general linear programming problem with integer variables is NP-complete. Even very restricted cases like the knapsack problem are. Unless what you have in mind is a very specialized case, asking for a polynomial solution is out. You'd need to specify your problem a lot more (and be lucky) if you are to get any help. $\endgroup$
    – vonbrand
    Aug 7, 2019 at 14:57
  • 1
    $\begingroup$ @vonbrand thank you. I have a book on integer programming now that talks about the complexity classes. By Schrijver. It's actually one of the best books I've ever read. Some of the problems are solvable polynomial time and some are considered perhaps only solvable in exponential time. $\endgroup$
    – Daniel Donnelly
    Aug 7, 2019 at 18:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.