← All posts

2-ASP(Q) with weak constraints: complexity and Casper implementation

A quantified ASP fragment for optimization up to Δ₃ᵖ—tight complexity results plus CEGAR in the Casper system.

Tags
researchsoftware engineering
2-ASP(Q) with weak constraints: complexity and Casper implementation
Contents

In brief

ASP(Q) adds quantifiers over answer sets to ASP. The 2-ASP(Q)^w fragment captures optimization up to Δ₃ᵖ with a full complexity map and a working solver story.

What they studied

Theory: complete complexity of main tasks for 2-ASP(Q)^w. Practice: CEGAR in Casper for optimal quantified answer sets.

Key findings

  • Practically relevant fragment, not theory-only.
  • Tailored CEGAR succeeds on hard cross-domain benchmarks.
  • Tight completeness results for core problems.

What this means for developers

Consider ASP(Q) for nested quantifier optimization; weak constraints model soft goals; CEGAR patterns transfer to other refinement loops.

Limitations

Declarative logic niche—not typical microservice tooling.