Paper 2015/985

Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system

Koh-ichi Nagao

Abstract

Koster shows that the problem for deciding whether the value of Semaev's formula $S_m(x_1,...,x_m)$ is $0$ or not, is NP-complete. This result directly does not means ECDLP being NP-complete, but, it suggests ECDLP being NP-complete. Further, Semaev shows that the equations system using $m-2$ number of $S_3(x_1,x_2,x_3)$, which is equivalent to decide whether the value of Semaev's formula $S_m(x_1,...,x_m)$ is $0$ or not, has constant(not depend on $m$ and $n$) first fall degree. So, under the first fall degree assumption, its complexity is poly in $n$ ($O(n^{Const})$).And so, suppose $P\ne NP$, which almost all researcher assume this, it has a contradiction and we see that first fall degree assumption is not true. Koster shows the NP-completeness from the group belonging problem, which is NP-complete, reduces to the problem for deciding whether the value of Semaev's formula $S_m(x_1,...,x_m)$ is $0$ or not, in polynomial time. In this paper, from another point of view, we discuss this situation. Here, we construct some equations system defined over arbitrary field $K$ and its first fall degree is small, from any 3SAT problem. The cost for solving this equations system is polynomial times under the first fall degree assumption. So, 3SAT problem, which is NP-complete, reduced to the problem in P under the first fall degree assumption. Almost all researcher assume $P \ne NP$, and so, it concludes that the first fall degree assumption is not true. However, we can take $K=\bR$(not finite field. It means that 3SAT reduces to solving multivariable equations system defined over $\R$ and there are many method for solving this by numerical computation. So, I must point out the very small possibility that NP complete problem is reduces to solving cubic equations equations system over $\bR$ which can be solved in polynomial time.