Record Details

On The Complexity Of Grobner Basis And Border Basis Detection

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title On The Complexity Of Grobner Basis And Border Basis Detection
 
Creator Prabhanjan, V A
 
Subject Computational Algebra
Grobner Bases
Border Bases
Border Basis Detection (BBD)
Computational Complexity
Rainbow Connectivity
Grober Basis Detection (GBD)
Polynomial Equations
Computer Science
 
Description The theory of Grobner bases has garnered the interests of a large number of researchers in computational algebra due to its applications not only in mathematics but also in areas like control systems, robotics, cryptography to name a few. It is well known that the computation of Grobner bases takes time doubly exponential in the number of indeterminates rendering it impractical in all but a few places.The current known algorithms for Grobner bases depend on the term order over which Grobner bases is computed. In this thesis, we study computational complexity of some problems in computational ideal theory. We also study the algebraic formulation of combinatorial optimization problems.
Gritzmann and Sturmfels (1993) posed the following question: Given a set of generators, decide whether it is a Gr¨obner bases with respect to some term order. This problem, termed as the Grobner Basis Detection(GBD)problem, was introduced as an application of Minkowski addition of polytopes. It was shown by Sturmfels and Wiegelmann (1997) that GBD is NP-hard. We study the problem for the case of zero-dimensional ideals and show that the problem is hard even in this special case. We study the detection problem in the case of border bases which are an alternative to Grobner bases in the case of zero dimensional ideals. We propose the Border Basis Detection(BBD) problem which is defined as follows: Given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. It is shown that BBD is NP-complete.
We also formulate the rainbow connectivity problem as a system of polynomial equations such that solving the polynomial system yields a solution to it. We give an alternate formulation of the rainbow connectivity problem as a membership problem in polynomial ideals.
 
Contributor Dukkipati, Ambedkar
 
Date 2013-06-14T10:24:45Z
2013-06-14T10:24:45Z
2013-06-14
2011-08
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/2056
http://etd.ncsi.iisc.ernet.in/abstracts/2652/G24951-Abs.pdf
 
Language en_US
 
Relation G24951