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.

$\endgroup$
  • 1
    $\begingroup$ Could you make it easier for others to help you? Please add an accessible url to your "certain problem". $\endgroup$ – Apass.Jack Aug 1 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$ – Shine On You Crazy Diamond Aug 1 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$ – Shine On You Crazy Diamond Aug 1 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 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$ – Shine On You Crazy Diamond Aug 7 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.