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$
1
  • $\begingroup$ Not a coursework. Winter project. It's half done, answers to this question will help me a lot. $\endgroup$ Dec 21, 2019 at 14:58

1 Answer 1

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.

$\endgroup$
8
  • $\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$ Dec 21, 2019 at 13:03
  • $\begingroup$ @anjansamanta A reduction is covered on the first page of this set of notes. $\endgroup$ Dec 21, 2019 at 23:53
  • $\begingroup$ Thanks. And from where you have concluded Grobner basis is EXPSPACE complete and the containment relation? $\endgroup$ Dec 22, 2019 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$ Dec 22, 2019 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$ Dec 22, 2019 at 23:06

Your Answer

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

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