navokoj_sat_2024

一个精心策划的布尔可满足性（SAT）CNF实例基准测试套件，用于评估现代SAT求解器的性能、泛化能力和鲁棒性。包含工业、合成、组合和竞赛风格问题的多样化混合。适用于研究、可重复比较和求解器开发。

原始信息汇总

Navokoj SAT 2024 数据集概述

基本信息

• 数据集名称: Navokoj SAT 2024
• 数据集描述: 一个精心策划的布尔可满足性（SAT）CNF实例基准测试套件，用于评估现代SAT求解器的性能、泛化能力和鲁棒性。包含工业、合成、组合和竞赛风格问题的多样化组合。适用于研究、可重复比较和求解器开发。
• 语言: 英语 (en)
• 许可证: CC-BY-4.0
• 任务类别: 其他 (other)
• 标签: sat, cnf, solver-benchmark, algorithm-comparison, performance-benchmark, computational-complexity, satisfiability
• 数据规模: 1K<n<10K
• 数据文件:
  • 分割: train
  • 路径: "sat_benchmark_final_verified.csv"

数据集内容

• 总问题数: 4,199 个 SAT 实例
• 测试日期: 2025年12月2日
• 批次大小: 每批次 50 个问题
• 总批次: 每个引擎 84 批次

引擎性能总结

Nano 引擎

• 完美解决率: 3.24% (136 个问题)
• 平均满意度: 96.41%
• 处理时间: 672.23 秒
• 吞吐量: 6.25 个问题/秒

Mini 引擎

• 完美解决率: 31.36% (1,317 个问题)
• 平均满意度: 99.55%
• 处理时间: 394.65 秒
• 吞吐量: 10.64 个问题/秒

Pro 引擎

• 完美解决率: 92.57% (3,887 个问题)
• 平均满意度: 99.92%
• 处理时间: 531.72 秒
• 吞吐量: 7.90 个问题/秒

文件结构

数据集包含三个综合结果文件：

• nano_engine_all_files_comprehensive.json - Nano 引擎的完整结果
• mini_engine_all_files_comprehensive.json - Mini 引擎的完整结果
• pro_engine_all_files_comprehensive.json - Pro 引擎的完整结果

每个 JSON 文件包含：

• test_metadata: 摘要统计信息和计时信息
• performance_metrics: 详细的性能分析
• comparison_with_other_engines: 相对性能比较
• batch_results: 所有 4,199 个实例的单个问题结果

数据来源

• 数据集获取自：https://zenodo.org/records/15125952
• 所有引擎均在 https://navokoj.shunyabar.foo/ 上使用三种物理启发的优化引擎（Nano, Mini, Pro）进行测试。
• 所有结果均可通过 https://navokoj.shunyabar.foo/docs/ 的 API 公开验证。

搜集汇总

数据集介绍

构建方式

在布尔可满足性问题的研究领域，Navokoj SAT 2024基准套件通过精心筛选与整合，构建了一个包含4,199个CNF实例的多样化集合。该数据集融合了工业应用、合成生成、组合优化及竞赛风格的问题，确保了实例的广泛代表性。构建过程中，所有问题均经过统一验证，并以每批50个实例的标准化流程进行处理，为后续的性能评估提供了可靠且一致的基础。

使用方法

研究人员可通过数据集中的JSON文件直接访问各引擎的完整结果，包括元数据、性能指标及批次详情。使用该数据集时，可进行可重复的求解器比较，评估算法在工业与合成问题上的表现。独立验证可通过提供的API接口完成，确保结果的可信度。数据集适用于SAT求解器的开发、基准测试以及计算复杂性研究，为相关领域提供了坚实的实证基础。

背景与挑战

背景概述

布尔可满足性问题作为计算复杂性理论的核心，是NP完全问题的典型代表，其求解算法的性能评估一直是理论计算机科学的关键议题。Navokoj SAT 2024基准测试套件由Navokoj团队于2024年构建，旨在为现代SAT求解器提供一个全面、多样化的性能评估平台。该数据集精心整合了工业应用、合成生成、组合优化及竞赛风格等不同类型的合取范式实例，共计4199个问题，其核心研究目标在于系统性地检验求解器在处理异构问题时的泛化能力、求解效率与鲁棒性。通过引入非交换几何与统计力学等物理学启发的优化引擎，该数据集不仅推动了SAT求解算法在跨学科方法上的创新探索，也为可重复性比较与求解器开发设立了新的基准，对自动推理与形式验证领域产生了显著影响。

当前挑战

该数据集致力于应对布尔可满足性求解领域的两大核心挑战：一是如何设计能够有效处理大规模、高复杂度CNF实例的通用求解算法，以克服NP完全问题固有的计算困难；二是如何构建一个均衡覆盖各类问题特征的基准测试集，以真实反映求解器在工业实践与理论极限场景下的综合性能。在构建过程中，研究人员面临的主要挑战包括：从海量候选问题中筛选出具有代表性与区分度的实例，确保数据集的多样性与无偏性；设计统一、可复现的批量测试流程，以消除实验环境差异对性能比较的干扰；以及建立公开可验证的API接口，保障结果的可审计性与透明度，从而为学术研究与工程应用提供可靠依据。

常用场景

经典使用场景

在可满足性理论的研究领域，Navokoj SAT 2024基准套件为评估现代SAT求解器的性能、泛化能力与鲁棒性提供了标准化的测试平台。该数据集精心整合了工业、合成、组合及竞赛风格的多样化CNF实例，使得研究者能够系统性地对比不同求解算法在复杂布尔约束下的表现。通过统一的批量处理流程，它确保了实验的可重复性与公平性，成为推动SAT求解技术前沿发展的核心工具。

解决学术问题

该数据集有效应对了SAT求解研究中长期存在的性能评估难题，为量化求解器的精确解率、处理速度与求解质量提供了可靠依据。它助力学术界深入探究计算复杂性理论中的NP完全问题，并促进了基于非交换几何与统计力学等跨学科方法的创新。通过公开可验证的结果，该数据集增强了研究透明度，为算法比较与理论分析奠定了坚实基础。

实际应用

在实际工程场景中，Navokoj SAT 2024基准套件被广泛应用于硬件验证、软件测试与自动推理等关键领域。其涵盖的工业实例能够模拟真实世界的约束满足问题，为开发高可靠性求解系统提供性能参照。例如，在芯片设计的形式化验证中，该数据集帮助工程师优化求解策略，以应对大规模电路等价性检查等复杂任务，从而提升设计效率与正确性。

数据集最近研究

最新研究方向

在布尔可满足性问题领域，Navokoj SAT 2024基准套件的出现标志着SAT求解器评估正迈向更系统化与多样化的阶段。该数据集整合了工业、合成及组合类问题，为现代求解器的性能、泛化性与鲁棒性提供了全面测试平台。前沿研究聚焦于利用非交换几何与统计力学等物理启发式优化引擎，如Nano、Mini和Pro引擎，其在4199个实例上展现出高达92.57%的完美求解率，推动了跨学科方法在计算复杂性中的应用。这一进展不仅促进了求解器开发的重复性比较，还关联了当前人工智能中高效算法与硬件协同优化的热点，对自动驾驶、芯片验证等关键领域的可靠性与效率提升具有深远意义。