# Gröbner basis via integer programming

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?

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

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.
• 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... – Mark Dec 22 '19 at 23:04