A various neighborhood search with Bayesian rounding technique for Satisfiability problem
Abstract
A various neighborhood search with Bayesian rounding technique for Satisfiability problem
Incoming article date: 20.02.2018The article reports about approximation algorithm for Integer Factoriation Problem (IFP) using reduction to optimizing case of SAT problem with 3 literals per clause (MAX-3SAT). A continuous functional that equivivalent MAX-3SAT is builded and solved by simple iteration method with variable neighboordood search and Bayesian rounding. It shown that global minimum of the functional cannot be reached in almost samples because local extremums but arguments of ones can be compared with the exact solution. The experiments show that the developed gybrid algorithm improves earlier version developed by authors. Also this method is analyzed by quantum channels defense In systems of quantum key distribution. A typical structure of one is described.
Keywords: Integer Factorization Problem, an optimzed version of SAT problem (MAX-3SAT), various neighboorhood search, continuous functional of MAX-3SAT representation, quantum key distribution