Welcome to the resource topic for 2015/985
Title:
Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system
Authors: 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.
ePrint: https://eprint.iacr.org/2015/985
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .