2
$\begingroup$

I know that in general, polynomial satisfiability is NP; however, I'm curious to know what work has been done on special classes of polynomials, and in particular quadratic polynomials of multiple variables.

EDIT: Just to clarify, I want to know if the polynomial has a solution over the real numbers. By satisfiability, I mean if a system of polynomials has a solution, but here I am only concerned with one quadratic multivariate polynomial having a solution over the reals.

$\endgroup$
  • 1
    $\begingroup$ Over the reals, I presume? If so, then maybe there is a multi-variate analogue of Sturm sequences... $\endgroup$ – Per Alexandersson Nov 16 '13 at 9:22
  • 3
    $\begingroup$ Nick, so you know, it is considered good form to not simultaneously post to different stackexchanges (cstheory). $\endgroup$ – usul Nov 16 '13 at 14:10
  • $\begingroup$ I apologize, I'm rather new to these sites, I figured that the crowds would be fairly disjoint between the two. I'll try to avoid posting to two sites in the future. $\endgroup$ – Nick Nov 19 '13 at 5:04
6
$\begingroup$

I might be misunderstanding the question, but if the equation is homogeneous, then zero is a solution, if the homogeneous (degree 2) part is an indefinite quadratic form, then the equation has a solution, if the homogeneous part is definite (say, wlog, positive definite, then checking if the minimum is negative reduces to an eigenvalue problem, and is certainly polynomial time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I've updated the problem description. I apologize, I meant that the quadratic polynomial has a real solution. I'm curious about checking if the minimum is negative, would that work to solve the problem? I'm understanding that you mean using the method of lagrange multipliers, but I'm curious how that would tell whether or not it has a real solution? $\endgroup$ – Nick Nov 19 '13 at 5:11
  • 1
    $\begingroup$ If the quadratic term is positive definite, you know that the polynomial is positive at infinity. So if the minimum is negative, intermediate value theorem is your friend. $\endgroup$ – Igor Rivin Nov 19 '13 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.