<p>The propositional model counting problem #SAT asks to compute the number of satisfying assignments for a given propositional formula. Recently, three #SAT proof systems <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\textsf{kcps}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">kcps</mi> </math></EquationSource> </InlineEquation> (knowledge compilation proof system), <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textsf{MICE}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">MICE</mi> </math></EquationSource> </InlineEquation> (model counting induction by claim extension), and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textsf{CPOG}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">CPOG</mi> </math></EquationSource> </InlineEquation> (certified partitioned-operation graphs) have been introduced with the aim to model #SAT solving and enable proof logging for solvers. A fourth system, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\textsf{CLIP}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">CLIP</mi> </math></EquationSource> </InlineEquation> (circuit linear introduction proposition), is a very powerful proof system of theoretical interest. Prior to this paper, it was only known that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\textsf{CLIP}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">CLIP</mi> </math></EquationSource> </InlineEquation> simulates the three other systems. All the remaining relations between the systems have been unclear and very few proof complexity results are known. We completely determine the simulation order of the four systems, establishing that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\textsf{CPOG}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">CPOG</mi> </math></EquationSource> </InlineEquation> simulates both <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\textsf{MICE}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">MICE</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\textsf{kcps}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">kcps</mi> </math></EquationSource> </InlineEquation>, while <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\textsf{MICE}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">MICE</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\textsf{kcps}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">kcps</mi> </math></EquationSource> </InlineEquation> are exponentially incomparable. This implies that <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\textsf{CPOG}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">CPOG</mi> </math></EquationSource> </InlineEquation> is strictly stronger than the other two systems.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Relative Strength of #SAT Proof Systems

  • Olaf Beyersdorff,
  • Johannes K. Fichte,
  • Markus Hecher,
  • Tim Hoffmann,
  • Lea Kasche

摘要

The propositional model counting problem #SAT asks to compute the number of satisfying assignments for a given propositional formula. Recently, three #SAT proof systems \(\textsf{kcps}\) kcps (knowledge compilation proof system), \(\textsf{MICE}\) MICE (model counting induction by claim extension), and \(\textsf{CPOG}\) CPOG (certified partitioned-operation graphs) have been introduced with the aim to model #SAT solving and enable proof logging for solvers. A fourth system, \(\textsf{CLIP}\) CLIP (circuit linear introduction proposition), is a very powerful proof system of theoretical interest. Prior to this paper, it was only known that \(\textsf{CLIP}\) CLIP simulates the three other systems. All the remaining relations between the systems have been unclear and very few proof complexity results are known. We completely determine the simulation order of the four systems, establishing that \(\textsf{CPOG}\) CPOG simulates both \(\textsf{MICE}\) MICE and \(\textsf{kcps}\) kcps , while \(\textsf{MICE}\) MICE and \(\textsf{kcps}\) kcps are exponentially incomparable. This implies that \(\textsf{CPOG}\) CPOG is strictly stronger than the other two systems.