Departmental Bulletin Paper 3SATの3次低first fall degree多変数方程式系への多項式時間帰着
3SAT ノ 3ジ テイ first fall degree タヘンスウ ホウテイシキケイ エノ タコウシキ ジカン キチャク
Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system

長尾, 孝一

59pp.1 - 5 , 2016-03 , 関東学院大学工学会
ISSN:03685373
NCID:AN00045764
Description
Recently, there are many researches [5] [3] [7] [4] that, under the first fall degree assumption, the complexity of ECDLP over pn where p is small prime and the extension degree n is input size, is subexponential. However, from the recent research, the first fall degree assumption seems to be doubtful. Koster et al. [2] shows that the problem for deciding whether the value of Semaev's formula Sm (x1, ..., xm) is 0 or not, is NP-complete. This result directly does not means ECDLP being NPcomplete, but, it suggests ECDLP being NP-complete. Further, in [7], Semaev shows that the equations system using m−2 number of S3 (x1, x2, x3), which is equivalent to decide whether the value of Semaev's formula Sm (x1, ..., xm) 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 (i.e., O (nConst)). And so, suppose P ≠ NP, which almost all researcher assume this, it has a contradiction and we see that first fall degree assumption is not true. Koster et al. 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 Sm (x1, ..., xm) 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 ≠ NP, and so, it concludes that the first fall degree assumption is not true. However, we can take K = . It means that 3SAT reduces to solving multivariable equations system defined over 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 which can be solved in polynomial time.
Full-Text

http://library.kanto-gakuin.ac.jp/e-Lib/bdyview.do?bodyid=NI30001051&elmid=Body&lfname=link/001.pdf

Number of accesses :  

Other information