Complexity of membership problems of different types of polynomial ideals

Ernst W. Mayr; Stefan Toman

doi:10.1007/978-3-319-70566-8_20

Complexity of membership problems of different types of polynomial ideals

Ernst W. Mayr, Stefan Toman

Informatics 14 - Chair of Algorithms and Complexity

Technical University of Munich

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

5 Scopus citations

Abstract

We survey degree bounds and complexity classes of the word problem for polynomial ideals and related problems. The word problem for general polynomial ideals is known to be exponential space-complete, but there are several interesting subclasses of polynomial ideals that allow for better bounds.We review complexity results for polynomial ideals with low degree, toric ideals, binomial ideals, and radical ideals. Previously known results as well as recent findings in our project “Degree Bounds for Gröbner Bases of Important Classes of Polynomial Ideals and Efficient Algorithms” are presented.

Original language	English
Title of host publication	Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory
Publisher	Springer International Publishing
Pages	481-493
Number of pages	13
ISBN (Electronic)	9783319705668
ISBN (Print)	9783319705651
DOIs	https://doi.org/10.1007/978-3-319-70566-8_20
State	Published - 1 Jan 2018

Keywords

Binomial ideal
Cellular decomposition
Computational complexity
Degree bound
Gröbner basis
Polynomial ideal
Radical
Thue system

Access to Document

10.1007/978-3-319-70566-8_20

Cite this

@inbook{159b691837cf4c2596c082f7c7aadb69,

title = "Complexity of membership problems of different types of polynomial ideals",

abstract = "We survey degree bounds and complexity classes of the word problem for polynomial ideals and related problems. The word problem for general polynomial ideals is known to be exponential space-complete, but there are several interesting subclasses of polynomial ideals that allow for better bounds.We review complexity results for polynomial ideals with low degree, toric ideals, binomial ideals, and radical ideals. Previously known results as well as recent findings in our project “Degree Bounds for Gr{\"o}bner Bases of Important Classes of Polynomial Ideals and Efficient Algorithms” are presented.",

keywords = "Binomial ideal, Cellular decomposition, Computational complexity, Degree bound, Gr{\"o}bner basis, Polynomial ideal, Radical, Thue system",

author = "Mayr, {Ernst W.} and Stefan Toman",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2017.",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-70566-8_20",

language = "English",

isbn = "9783319705651",

pages = "481--493",

booktitle = "Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory",

publisher = "Springer International Publishing",

}

TY - CHAP

T1 - Complexity of membership problems of different types of polynomial ideals

AU - Mayr, Ernst W.

AU - Toman, Stefan

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2017.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We survey degree bounds and complexity classes of the word problem for polynomial ideals and related problems. The word problem for general polynomial ideals is known to be exponential space-complete, but there are several interesting subclasses of polynomial ideals that allow for better bounds.We review complexity results for polynomial ideals with low degree, toric ideals, binomial ideals, and radical ideals. Previously known results as well as recent findings in our project “Degree Bounds for Gröbner Bases of Important Classes of Polynomial Ideals and Efficient Algorithms” are presented.

AB - We survey degree bounds and complexity classes of the word problem for polynomial ideals and related problems. The word problem for general polynomial ideals is known to be exponential space-complete, but there are several interesting subclasses of polynomial ideals that allow for better bounds.We review complexity results for polynomial ideals with low degree, toric ideals, binomial ideals, and radical ideals. Previously known results as well as recent findings in our project “Degree Bounds for Gröbner Bases of Important Classes of Polynomial Ideals and Efficient Algorithms” are presented.

KW - Binomial ideal

KW - Cellular decomposition

KW - Computational complexity

KW - Degree bound

KW - Gröbner basis

KW - Polynomial ideal

KW - Radical

KW - Thue system

UR - http://www.scopus.com/inward/record.url?scp=85046586795&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-70566-8_20

DO - 10.1007/978-3-319-70566-8_20

M3 - Chapter

AN - SCOPUS:85046586795

SN - 9783319705651

SP - 481

EP - 493

BT - Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory

PB - Springer International Publishing

ER -

Complexity of membership problems of different types of polynomial ideals

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this