1
$\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.

Improve this question
$\endgroup$
5
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 2:03

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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