SuperAPI AI 工具集

three-match

通用与其它

查看项目

更新于 10-16 08:07

技能介绍

用途:three-match 把 3-SAT 归约为三着色,再归约为彩色子图同构,用 3-MATCH gadget 在局部强制约束,宣称局部测地线约束满足即可保证全局 3-SAT 解正确。

主要能力:提供 ThreeMatch gadget(三色局部约束,GF(3) 和 ≡ 0 mod 3)、NonBacktrackingGeodesic(素数路径,μ(n)≠0)、ColoredSubgraphGadget(3-SAT 子句归约,add_clause 后 build_gadgets!)、BackAndForthFilter(Möbius 反演双向过滤)。核心判据为 v₃(|a-b|)≥d 等三条 3-adic 估值条件。

使用方式:Ruby 中 require 'three_match_geodesic_gadget',用 ThreeMatch.new(seed:) 创建 gadget,调用 gf3_conserved?、matches_at_depth?(1) 验证;用 NonBacktrackingGeodesic.new(seed:, length:).generate! 生成路径并检查 prime?。命令行可用 just three-match、just test-three-match、just unworld-match。可与 Unworld 的 ThreeMatchChain 做种子链式集成。

适用场景:3-SAT 归约演示、彩色子图同构 gadget 构造、以及将类型稳定的路径缓存类比为非回溯测地线的内联缓存验证。

限制:资料未提供安装步骤、依赖版本、性能数据与许可信息;文中 93-113x 加速等基准结论来自资料自述,未提供可复现细节。