A non-NP-complete algorithm for a quasi-fixed polynomial problem. (English) Zbl 1276.39012

Summary: Let \(F : \mathbb R \times \mathbb R \to \mathbb R\) be a real-valued polynomial function of the form \(F(x, y) = \sum^s_{i = 0}f_i(x)y^i\), with degree of \(y\) in \(F(x, y) = s \geq 1\), \(x \in \mathbb R\). An irreducible real-valued polynomial function \(p(x)\) and a nonnegative integer \(m\) are given to find a polynomial function \(y(x) \in \mathbb R[x]\) satisfying the following expression: \(F(x, y(x)) = cp^m(x)\) for some constant \(c \in \mathbb R\). The constant \(c\) is dependent on the solution \(y(x)\), namely, a quasi-fixed (polynomial) solution of the polynomial-like equation \((\ast)\). In this paper, we provide a non-NP-complete algorithm to solve all quasi-fixed solutions if the equation \((\ast)\) has only a finite number of quasi-fixed solutions.


39B22 Functional equations for real functions
12D99 Real and complex fields
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Lenstra, A. K., Factoring multivariate polynomials over algebraic number fields, SIAM Journal on Computing, 16, 3, 591-598, (1987) · Zbl 0636.12005
[2] Tung, S. P., Near solutions of polynomial equations, Acta Arithmetica, 123, 2, 163-181, (2006) · Zbl 1152.11012
[3] Tung, S. P., Algorithms for near solutions to polynomial equations, Journal of Symbolic Computation, 44, 10, 1410-1424, (2009) · Zbl 1201.13009
[4] Lai, H.-C.; Chen, Y.-C., A quasi-fixed polynomial problem for a polynomial function, Journal of Nonlinear and Convex Analysis, 11, 1, 101-114, (2010) · Zbl 1206.47050
[5] Tung, S. P., Approximate solutions of polynomial equations, Journal of Symbolic Computation, 33, 2, 239-254, (2002) · Zbl 1046.13020
[6] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra, (2003), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1055.68168
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.