0
$\begingroup$

Every conjunctive normal form (CNF) formula can be converted to nonlinear system of equations, where each clause becomes an equation in the system and:

If A and B are logical/boolean variables and defined as A∈{T,F} ∧ B∈{T,F} or (A,B)∈{T,F}2 where

{T,F}2={T,F}⨯{T,F} = {(T,T),(T,F),(F,T),(FF)}

Then:

A=x, ¬A=1-x, B=y, ¬B=1-y and A∨B=x+y-x•y

That's how the left side of each nonlinear equation in the system is computed.

The right side of each nonlinear equation in the system is obviously the constant natural number 1.

Finding a solution to this nonlinear system of equations is finding satisfying assignment to the given CNF formula.

That way SAT is reduced to the problem of solving nonlinear system of equations in polynomial time, thus the problem of solving nonlinear system of equations is NP-Hard, because of the fact that SAT is NP-Complete.

But I think that there already exist algorithms that solve nonlinear system of equations in polynomial time and space complexity, if so then also SAT can be solved in polynomial time and space complexity too.

Do I wrong in everything I said?

It sounds too good to be true and

If it's too good to be true, something's wrong.

quote from John Allison.

$\endgroup$
  • 1
    $\begingroup$ Why do you think that "there already exist algorithms that solve nonlinear system of equations in polynomial time and space complexity"? Also, there are many different kinds of nonlinearity. Can you provide any pointers or citations to what you're talking about? $\endgroup$ – mhum Jul 27 '17 at 1:15
  • $\begingroup$ That was only a thought/opinion. I don't really know, that's why I am asking. Also didn't you understand how each clause is converted to an equation? Didn't you understand how positive and negative literals are converted to variables? How disjunction becomes addition, subtraction and multiplication? $\endgroup$ – Farewell Stack Exchange Jul 27 '17 at 1:17
  • 1
    $\begingroup$ The conversion that you provide is fairly conventional. The claim that there already exist algorithms that solve nonlinear system of equations in polynomial time is not. Which is why I was asked for a reference or pointer for that claim. $\endgroup$ – mhum Jul 27 '17 at 1:30
  • $\begingroup$ I have neither reference nor pointer for that claim. I asked if does exist polynomial algorithms for that and you answered that doesn't. This is correct, because problem is NP-Hard indeed. You can post this comment as answer to my question. $\endgroup$ – Farewell Stack Exchange Jul 27 '17 at 1:42
  • 1
    $\begingroup$ Ok. The way it was phrased made it seem that you had something specific in mind (i.e.: "I think that ...") rather that as a question about whether such a thing exists. $\endgroup$ – mhum Jul 27 '17 at 2:03
3
$\begingroup$

It is not currently known whether or not a polynomial algorithm exists to solve these systems of nonlinear equations because, as the reduction provided shows, if such a thing were to exist, it would show that $NP = P$ which remains yet unknown.

$\endgroup$

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.