Another approach to decide on real root existence for univariate Polynomials, and a multivariate extension for 3-SAT

2008/02/29 by Chermakani, Deepak Ponvel
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.0803.0018

Abstract

We present six Theorems on the univariate real Polynomial, using which we develop a new algorithm for deciding the existence of atleast one real root for univariate integer Polynomials. Our algorithm outputs that no positive real root exists, if and only if, the given Polynomial is a factor of a real Polynomial with positive coefficients. Next, we define a transformation that transforms any instance of 3-SAT into a multivariate real Polynomial with positive coefficients, if and only if, the instance is not satisfiable.

Related

• Real Polynomial Root-finding by Means of Matrix and Polynomial Iterations
• Could René Descartes have known this?
• An iterative approach for real roots of polynomials
• Computing Real Roots of Real Polynomials
• Three complete deterministic polynomial algorithms for 3SAT