2019/07/23 by Tomoya Machide, Machide, Tomoya
Computer Science · Mathematics · #03D15 #03G05 #06E30 #08A40 (Primary) #13P15 #68W30 (Secondary) #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Commutative Algebra (math.AC) #FOS: Mathematics #Formal Methods in Verification #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.1907.09686
openalex publication_date 2019/07/23 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
It is known a method for converting a system of Boolean polynomial equations\nto a single Boolean polynomial equation with less variables. In this paper, we\nshow a formula for systems of Boolean polynomial equations which is based on\nthe method. The formula has a structure of binary tree, and conforms to De\nMorgan's duality. Using the formula, we prove a computational complexity result\nwith a parameter for solving systems. The parameter is the bandwidth in matrix\nand graph theories: to be precise, the definition follows convention in matrix\nand the value depends on the order of variables. We also apply the result to\nthe NP-complete problems, SAT and graph list-coloring, to show that these\nproblems are fixed parameter tractable by bandwidth.\n