计算命题公式的极小模型在人工智能推理系统中是一项必不可少的任务．然而，即使是正CNF（conjunctive normal form）公式，其极小模型的计算和验证都不是易处理的．当前，计算CNF公式极小模型的主要方法之一是将其转换为析取逻辑程序...
详细信息
计算命题公式的极小模型在人工智能推理系统中是一项必不可少的任务．然而，即使是正CNF（conjunctive normal form）公式，其极小模型的计算和验证都不是易处理的．当前，计算CNF公式极小模型的主要方法之一是将其转换为析取逻辑程序后用回答集程序(answer set programming，ASP)求解器计算其稳定模型/回答集．针对计算CNF公式的极小模型的问题，提出一种基于可满足性(satisfiability problem，SAT)求解器的计算极小模型的方法MMSAT；然后结合最近基于极小归约的极小模型验证算法CheckMinMR，提出了基于极小模型分解的计算极小模型方法MRSAT；最后对随机生成的大量的3CNF公式和SAT国际竞赛上的部分工业基准测试用例进行测试，实验结果表明，MMSAT和MRSAT对随机3CNF公式和SAT工业测试用例都是有效的，且计算极小模型的速度都明显快于最新版的clingo，并且在SAT工业实例上发现了clingo有计算出错的情况，而MMSAT和MRSAT则更稳定．实验代码及数据地址：https://***/zhangli-hub123/minimal-model．
传统的委托计算需要额外开销验证计算结果的正确性,导致委托计算效率较低、开销较大.针对此问题,结合博弈论与理性信任建模(rational trust modeling,简称RTM)的思想,提出了基于理性信任模型的理性委托计算协议.通过设置恰当的效用函数,激励计算方诚实执行协议,以此来保证计算结果的可靠性.首先,基于理性信任建模的思想构造理性信任模型,将服务器的生存周期作为效用函数的参数,设计满足委托计算参与者利益的效用函数,并分析协议中参与者的行为策略,当参与者采取"诚实"策略时,可以得到理性委托计算的纳什均衡点;其次,利用改进的NTRU(number theory research unit)公钥密码体制实现速度快、安全性高、具有抵抗量子计算攻击的能力的优点,结合Pedersen承诺方案,设计理性委托计算协议;最后,从正确性、安全性与性能这3个方面对协议进行分析,并通过实验证明生存周期对参与者效用的影响.结果表明,该协议可有效保证计算结果的可靠性.
暂无评论