A Polynomial Time Complexity Bound for Computations on Curves

DOI10.1137/S0097539796300969MaRDI QIDQ4210172zbMATH OpenFDO

Authors P. G. Walsh

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539796300969

zbMATH Keywords

complexitycomputation of the genus of an algebraic curvePuiseux expansion

Mathematics Subject Classification ID

Special algebraic curves and curves of low genus (14H45) Computational aspects of algebraic curves (14Q05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Polynomial complexity algorithms for computational problems in the theory of algebraic curves
• On the complexity of computing with planar algebraic curves
• scientific article; zbMATH DE number 5154
• scientific article; zbMATH DE number 953020
• scientific article; zbMATH DE number 6322905
• scientific article; zbMATH DE number 3983069
• On the complexity of parametrizing curves
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• scientific article; zbMATH DE number 69493
• Complexity of computation of embedded resolution of algebraic curves

Cites work

• A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function
• A quantitative version of Runge's theorem on diophantine equations
• Approximation to certain transcendental decimal fractions by algebraic numbers
• Eisenstein's theorem on power series expansions of algebraic functions
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 3834090 (Why is no real title available?)
• scientific article; zbMATH DE number 3858405 (Why is no real title available?)
• scientific article; zbMATH DE number 3920595 (Why is no real title available?)
• scientific article; zbMATH DE number 3342122 (Why is no real title available?)
• Irreducibility testing over local fields
• The Computational Complexity of the Resolution of Plane Curve Singularities

Cited in

(8)

• On the complexity of finite subgraphs of the curve graph
• Computation of étale cohomology on curves in single exponential time
• Quantum computation of zeta functions of curves
• Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length
• scientific article; zbMATH DE number 4180354 (Why is no real title available?)
• scientific article; zbMATH DE number 6322905 (Why is no real title available?)
• A polynomial-time computable curve whose interior has a nonrecursive measure
• A polynomial-time algorithm for computing the yolk in fixed dimension

This page was built for publication: A Polynomial Time Complexity Bound for Computations on Curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210172)