1
$\begingroup$

I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating this into an integer program and then solving it by the usual branch & bound method?

The professor teaching the course has told me to think about it, but I have no clue. Any suggessions?

$\endgroup$
  • $\begingroup$ Not a coursework. Winter project. It's half done, answers to this question will help me a lot. $\endgroup$ – anjan samanta Dec 21 '19 at 14:58
3
$\begingroup$

ILP is $NP$-complete, while computing a Grobner Basis is $EXPSPACE$-complete. As one has the containments $NP\subseteq PSPACE\subsetneq EXPSPACE$, one should expect that you can reduce ILP to computing a Grobner basis, but not the other direction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't know about NP complete. Could you please suggest me or give me the link of any article/book related to this? I will be thankful to you. $\endgroup$ – anjan samanta Dec 21 '19 at 13:03
  • $\begingroup$ @anjansamanta A reduction is covered on the first page of this set of notes. $\endgroup$ – Mark Dec 21 '19 at 23:53
  • $\begingroup$ Thanks. And from where you have concluded Grobner basis is EXPSPACE complete and the containment relation? $\endgroup$ – anjan samanta Dec 22 '19 at 7:15
  • $\begingroup$ I haven't read this article (and am off campus so cannot quickly review it), but others source it for the EXPSPACE complete claim. The containment $PSPACE\subsetneq EXPSPACE$ follows from the space hierarchy theorem. It is worth mentioning the above reasoning only holds as you phrase the question as "Given any ideal, represent it as an ILP". Grobner Basis are very difficult to compute in the worst case, but are known to be more manageable than one might expect in particular cases... $\endgroup$ – Mark Dec 22 '19 at 23:04
  • $\begingroup$ I am no expert in the area, and have only seen this vaguely alluded to (see the second paragraph of this paper, for example). The situation seems similar to 3SAT being NP-hard but often solvable in practice. That being said, you can't hope for some standard reduction from Grobner Basis computations to ILP due to the reasoning I gave above. $\endgroup$ – Mark Dec 22 '19 at 23:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.