5
$\begingroup$

The problem of solving quadratic equations is as follows:

Suppose you are given a set of quadratic equations and are asked to find $0$-$1$ values for the variables such that all equations are satisfied. For example, consider the system $$x_1x_2-x_3 = 0$$ $$x_1x_3-x_1x_4+x_3x_4 = 1$$ $$x_1x_4-x_2x_3+x_1x_3 = 0$$ You may easily verify that the setting $$x_1=x_2=x_3=1$$ and $$x_4=0$$ satisfies all requirements.

I need to show that if we suppose that this problem is in P then the problem of integer factorization is also in P. I have no idea how to start. Please help me.

I know that the problem is in NP, because there is a polynomial verifier to it. I got stuck when I tried to find a polynomial reduction from the quadratic equation problem to integer factorization. I don't figure out how to "connect" from quadratic equations to integer factorization. I have tried to simplify the problem and construct a polynomial reduction from this problem to the problem of finding only one divisor of $n$, and if I do so, I could simply run this algorithm polynomial number of times to find the other divisors of $n$. So far I have failed at this.

$\endgroup$
  • $\begingroup$ Determining whether a set of quadratic equations has a solution is NP-complete. Integer factoring is in NP. $\endgroup$ – Yuval Filmus Aug 6 '17 at 20:59
  • $\begingroup$ Do you know how to prove that a problem is NP-complete? $\endgroup$ – D.W. Aug 7 '17 at 2:25
  • $\begingroup$ Try reduction from SAT to 0-1 quadratic equations. You have 3 operators $+, -, \cdot$ which can be converted to logical operators (or their combinations) $\lor, \land, \neg$ and vice versa. $\endgroup$ – rus9384 Aug 7 '17 at 9:43

Your Answer

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

Browse other questions tagged or ask your own question.