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?

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

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .