• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    On The Complexity Of Grobner Basis And Border Basis Detection

    View/Open
    G24951.pdf (624.2Kb)
    Date
    2013-06-14
    Author
    Prabhanjan, V A
    Metadata
    Show full item record
    Abstract
    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.
    URI
    https://etd.iisc.ac.in/handle/2005/2056
    Collections
    • Computer Science and Automation (CSA) [392]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV