BriefGPT - AI 论文速递
·
结构化的 d-DNNF 不封闭于否定
💡
原文中文，约300字，阅读约需1分钟。
📝
内容提要
结构化 d-DNNF、SDD 和 OBDD 之间存在可处理性转换和简洁性差距的问题。实验证明结构化 d-DNNF 不支持多项式时间的取反、析取和存在量词操作。存在一些函数，具有等价的多项式大小的结构化 d-DNNF，但没有等价的 SDD 表示。通过对算术电路（AC）的研究，将这个结果推广到 PSDD 和结构化 d-DNNF 的单调 AC 类似物之间，展示了简洁性差距。
🎯
关键要点
- 结构化 d-DNNF、SDD 和 OBDD 之间存在可处理性转换和简洁性差距的问题。
- 实验证明结构化 d-DNNF 不支持多项式时间的取反、析取和存在量词操作。
- 存在一些函数，具有等价的多项式大小的结构化 d-DNNF，但没有等价的 SDD 表示。
- 通过对算术电路（AC）的研究，将结果推广到 PSDD 和结构化 d-DNNF 的单调 AC 类似物之间。
- 展示了简洁性差距。
➡️
