Skip to main content
Clarify the question, spell it all out. Add a little more text that might make this easier to find via search as well.
Source Link

Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find a common zero of all of these polynomials? In other words, given $P$, can you find $x_1,\dots,x_n\in\mathbb{R}$ such that $p_i(x_1,\dots,x_n)=0$ for all $i$? I only need to find one solution.

I know that in the general case it isn't efficient(arbitrary degree polynomials) this can't be done efficiently. However, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.

Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find $x_1,\dots,x_n\in\mathbb{R}$?

I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.

Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find a common zero of all of these polynomials? In other words, given $P$, can you find $x_1,\dots,x_n\in\mathbb{R}$ such that $p_i(x_1,\dots,x_n)=0$ for all $i$? I only need to find one solution.

I know that in the general case (arbitrary degree polynomials) this can't be done efficiently. However, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.

Source Link
Arc
  • 263
  • 1
  • 2
  • 6

Can you efficiently solve a system of quadratic multivariate polynomials?

Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find $x_1,\dots,x_n\in\mathbb{R}$?

I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.