SHF: Small: IsoLator: Avoiding Isomorphic Graphs Effectively

SHF:小:IsoLator:有效避免同构图

基本信息

  • 批准号:
    1526760
  • 负责人:
  • 金额:
    $ 50万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2015
  • 资助国家:
    美国
  • 起止时间:
    2015-07-01 至 2019-06-30
  • 项目状态:
    已结题

项目摘要

Over the last two decades, the speed and capacity of Satisfiability (SAT) solvers has improved by several orders of magnitude, which enabled the verification and analysis of larger and more complex real world systems. However, a weaknesses of contemporary SAT solvers is their limited ability to obviate needless exploration of isomorphic parts of the search space. This research investigates an approach to significantly improve the performance of SAT solvers when applied to problems of graph theory. The approach taken in this project focuses on breaking all symmetries of SAT encodings of graph-related problems. The key new concept is the notion of isolators: propositional formulas that avoid evaluating multiple graphs in an isomorphism class. The project investigates several foundational questions: (1) how to construct perfect isolators which break all symmetries? (2) whether perfect isolators that are polynomial in the size of the corresponding graph problem exist? and (3) how perfect isolators boost SAT solver performance on hard graph-related problems?
在过去的二十年里,可满足性(SAT)求解器的速度和能力已经提高了几个数量级,这使得更大和更复杂的真实的世界系统的验证和分析。然而,当代SAT求解器的一个弱点是它们的能力有限,无法避免对搜索空间的同构部分进行不必要的探索。本研究探讨了一种方法,显着提高SAT求解器的性能时,适用于图论问题。在这个项目中采取的方法侧重于打破所有对称性的SAT编码的图形相关的问题。关键的新概念是隔离器的概念:避免在同构类中评估多个图的命题公式。该项目研究了几个基本问题:(1)如何构造打破所有对称性的完美隔离器?(2)是否存在完美的隔离器,多项式的大小相应的图的问题?以及(3)完美隔离器如何提高SAT求解器在与硬图相关的问题上的性能?

项目成果

期刊论文数量(1)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Strong Extension-Free Proof Systems
  • DOI:
    10.1007/s10817-019-09516-0
  • 发表时间:
    2020-03-01
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Heule, Marijn J. H.;Kiesl, Benjamin;Biere, Armin
  • 通讯作者:
    Biere, Armin
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Marienus Heule其他文献

Marienus Heule的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Marienus Heule', 18)}}的其他基金

SHF: Small: Synergy between Automated Reasoning and Interactive Theorem Proving
SHF:小:自动推理和交互式定理证明之间的协同作用
  • 批准号:
    2229099
  • 财政年份:
    2022
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF : Small: Certified Automated Reasoning with BDDs (CARB)
SHF:小型:经过 BDD 认证的自动推理 (CARB)
  • 批准号:
    2108521
  • 财政年份:
    2021
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: WLoS: Without Loss of Satisfaction
SHF:小:WLoS:不丧失满意度
  • 批准号:
    1910438
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: WLoS: Without Loss of Satisfaction
SHF:小:WLoS:不丧失满意度
  • 批准号:
    2015445
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: MaPaMaP: Massively Parallel Solving of Math Problems
SHF:小型:MaPaMaP:数学问题的大规模并行解决
  • 批准号:
    2006363
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: Mechanical Verification of QBF Results
SHF:小型:QBF 结果的机械验证
  • 批准号:
    2010951
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: MaPaMaP: Massively Parallel Solving of Math Problems
SHF:小型:MaPaMaP:数学问题的大规模并行解决
  • 批准号:
    1813993
  • 财政年份:
    2018
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: Mechanical Verification of QBF Results
SHF:小型:QBF 结果的机械验证
  • 批准号:
    1618574
  • 财政年份:
    2016
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
  • 批准号:
    10099896
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Collaborative R&D
"Small performances": investigating the typographic punches of John Baskerville (1707-75) through heritage science and practice-based research
“小型表演”:通过遗产科学和基于实践的研究调查约翰·巴斯克维尔(1707-75)的印刷拳头
  • 批准号:
    AH/X011747/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
Fragment to small molecule hit discovery targeting Mycobacterium tuberculosis FtsZ
针对结核分枝杆菌 FtsZ 的小分子片段发现
  • 批准号:
    MR/Z503757/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
Bacteriophage control of host cell DNA transactions by small ORF proteins
噬菌体通过小 ORF 蛋白控制宿主细胞 DNA 交易
  • 批准号:
    BB/Y004426/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
Windows for the Small-Sized Telescope (SST) Cameras of the Cherenkov Telescope Array (CTA)
切伦科夫望远镜阵列 (CTA) 小型望远镜 (SST) 相机的窗口
  • 批准号:
    ST/Z000017/1
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Research Grant
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
  • 批准号:
    2317251
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了