Est-il possible de résoudre le temps polynomial en le réduisant au problème de la résolution du système d'équations non linéaires?
-
04-11-2019 - |
Question
Chaque formule de forme normale conjonctive (CNF) peut être convertie en système non linéaire des équations, où chaque clause devient une équation dans le système et:
Si a et b sont des variables logiques / booléennes et définies comme a∈ {t, f} ∧ b∈ {t, f} ou (a, b) ∈ {t, f}2 où
{T, f}2= {T, f} ⨯ {t, f} = {(t, t), (t, f), (f, t), (ff)}
Alors:
A = x, ¬a = 1-x, b = y, ¬B = 1-y et a∨b = x + yx • y
C'est comme ça le la gauche côté de chaque équation non linéaire dans le système est calculé.
La droit côté de chaque équation non linéaire dans le système est évidemment Le numéro naturel constant 1.
Trouver une solution à ce système non linéaire d'équations consiste à trouver une affectation satisfaisante à la formule CNF donnée.
De cette façon, SAT est réduit au problème de la résolution du système non linéaire des équations en temps polynomial, donc le problème de la résolution du système non linéaire des équations est durs NP, en raison du fait que SAT est NP-Complete.
Mais je pense qu'il existe déjà des algorithmes qui résolvent le système non linéaire d'équations en temps polynomial et complexité spatiale, si c'est le cas, alors SAT peut également être résolu en temps polynomial et en complexité spatiale.
Ai-je du mal dans tout ce que j'ai dit?
Cela semble trop beau pour être vrai et
Si c'est trop beau pour être vrai, quelque chose ne va pas.
Citation de John Allison.
Pas de solution correcte