随机多比特翻转算法求解布尔多项式方程组可满足性问题
来源期刊:江西理工大学学报2018年第1期
论文作者:吕逸杰 刘芳 周婷 艾江俊 巫光福
文章页码:60 - 65
关键词:布尔多项式方程组;贪婪算法;随机多比特翻转算法;
摘 要:布尔多项式方程组求解问题是数学与计算机科学中的难解之一,极大布尔多项式方程组可满足性问题是一般布尔多项式方程组求解问题的扩展问题.为了解决极大布尔多项式方程组可满足性问题,首先,提出了一种可证明是否存在满足全部函数为0的解的贪婪算法,结果是不存在满足256个函数全部为0的解;其次,提出了一种基于低密度奇偶校验码,比特翻转译码算法与随机数相结合的随机多比特翻转算法.
吕逸杰,刘芳,周婷,艾江俊,巫光福
江西理工大学信息工程学院
摘 要:布尔多项式方程组求解问题是数学与计算机科学中的难解之一,极大布尔多项式方程组可满足性问题是一般布尔多项式方程组求解问题的扩展问题.为了解决极大布尔多项式方程组可满足性问题,首先,提出了一种可证明是否存在满足全部函数为0的解的贪婪算法,结果是不存在满足256个函数全部为0的解;其次,提出了一种基于低密度奇偶校验码,比特翻转译码算法与随机数相结合的随机多比特翻转算法.
关键词:布尔多项式方程组;贪婪算法;随机多比特翻转算法;