4
$\begingroup$

During the presentation (a talk) Answer Set Programming: Boolean Constraint Solving for Knowledge Representation and Reasoning Torsten Schaub (University of Postdam) stated around twenty-one minutes into the talk, "You can't translate an ASP (answer set program) into SAT (propositional formula) in a modular way...." continuing... "If you don't extend the language and if you translate ASP into SAT you risk an exponential blowup."

Is there an example that clearly shows that Answer Set Program to SAT translation is exponential.

PS: Allowed to use Plaisted Greenbaum encoding or Tseitin transformation.

Improve this question
$\endgroup$
2
  • $\begingroup$ factoring? or NP complete problem instances? $\endgroup$
    – vzn
    Dec 15, 2020 at 2:43
  • 1
    $\begingroup$ @vzn I am dealing with an NP-complete problem. $\endgroup$
    – Anton Menshov
    Dec 15, 2020 at 15:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.