Title | **Complexity of Gröbner basis detection and border basis detection** |

Author(s) | Prabhanjan V. Ananth, Ambedkar Dukkipati |

Type | Article in Journal |

Abstract | Gröbner basis detection (GBD) is defined as follows: given a set of polynomials, decide whether there exists–and if “yes” find–a term order such that the set of polynomials is a Gröbner basis. This problem was proposed by Gritzmann and Sturmfels (1993) [12] and it was shown to be NP-hard by Sturmfels and Wiegelmann. We investigate the computational complexity of this problem when the given set of polynomials are the generators of a zero-dimensional ideal. Further, we propose the Border basis detection (BBD) problem which is formulated as follows: given a set of generators of an ideal, decide whether the set of generators is a border basis of the ideal with respect to some order ideal. We analyse the complexity of this problem and prove it to be NP-complete. |

Keywords | Border bases, Zero-dimensional ideals, Gröbner basis detection, Complexity |

ISSN | 0304-3975 |

URL |
http://www.sciencedirect.com/science/article/pii/S0304397512007505 |

Language | English |

Journal | Theoretical Computer Science |

Volume | 459 |

Pages | 1 - 15 |

Year | 2012 |

Edition | 0 |

Translation |
No |

Refereed |
No |