Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?

cs.stackexchange https://cs.stackexchange.com/questions/79386

سؤال

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.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top