欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

布尔函数 python 布尔函数问题解决方案

最编程 2024-06-11 11:10:26
...


求解布尔方程(Boolean Equations)的4个高效baseline算法


求解布尔方程(Boolean Equations)是理论计算机中的基本问题之一;事实上,求解 个变量的 个非线性多项式方程组是一个基础的数学问题,受到了包括密码学界在内的各个理论计算机研究方向的广泛关注;众所周知,AI领域的计算机视觉和自然语言处理就有许多具体任务(比如人脸识别,语义分割)的baselines(也就是提供参考对比的基线模型/算法),那么自然研究求解布尔方程也有对应的baselines,今天我们就介绍当前最佳的4个高效baseline算法.

布尔函数python 布尔函数的求解问题_多项式_04

布尔方程组求解问题(Boolean PoSSo (polynomial system solving) Problem):给定一组布尔多项式 :

目标是找到解 对于 , 满足 . 其中:

它限定了每个变元的取值也在


算法分类

布尔方程组求解问题和计算机科学里的许多其他 NP-hard 问题都有联系(比如SAT问题,MILP整数规划问题等等);因此求解思路大致分为搜索求解,代数方法求解,问题变换求解三种基本思路,按照这样的划分,本文要介绍以下4种baseline算法:

  • BCS算法(Boolean Characteristic Set Algorithm)[1]:基于经典代数消元方法吴消元法的求解算法;
  • Groebner基算法[2]:基于多项式理想构造算法Groebner Basis的求解算法(基于SAGE V9.2的Polybori库实现);
  • FESLib库(Fast Exhaustive Search Algorithm)[3]:基于分治+解空间搜索的求解算法(复杂度是指数级别 );
  • 转SAT算法(Boolean Equations to SAT Algorithm)[4]:将布尔方程组问题转化为等价的SAT问题再使用SAT求解器求解的算法(基于Cryptominisat实现);

在本文中,我们主要侧重实现(所有代码均在Linux下编译实现),理论部分可以详见参考文献(如有需要,我会另外写博客来分别介绍这4篇工作的技术细节部分);


BCS算法(Boolean Characteristic Set Algorithm)

BCS算法 [1] 虽然基于吴消元法计算特征列,但是巧妙利用了布尔多项式的加法特点,克服了原方法里多项式膨胀的问题:

中做拟除 Pesudo-division: 利用多项式

上一篇: c 语言中 _bool 是什么意思

下一篇: 哪些 PHP 函数可以返回布尔值?

推荐阅读