Research map / Learning theory and algorithms / Combinatorial and search optimization
Characterizing Structural Hardness of Logic Programs: What Makes Cycles and Reachability Hard for Treewidth?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use reachability along cycles to encode SAT assignments as orderings | SAT-to-normal ASP reduction · SAT formulas with treewidth k | treewidth: k -> \mathcal{O}(\frac{k}{\log(k)}) | Helped |
| Bound the largest dependency-graph SCC by 2^{\mathcal{O}(k\cdot\log(k))} | Normal ASP consistency · Normal logic programs of treewidth k | runtime lower bound: 2^{o(k\cdot\log(k))}\cdot\poly(\Card{\text{\normalfont at}(\Pi)}) | Hurt |
| Bound the largest dependency-graph SCC by 2^{\mathcal{O}(k\cdot\log(k))} | Projected answer set counting · Normal logic programs of treewidth k | runtime lower bound: 2^{2^{o(k\cdot\log(k))}}\cdot\poly(\Card{\text{\normalfont at}(\Pi)}) | Hurt |
| Use ordering blocks of up to \iota elements in the reduction | SAT-to-normal ASP reduction for \iota-tight programs · SAT formulas with treewidth k | treewidth: k -> \mathcal{O}(\frac{k}{\log(\iota)}) | Helped |
| Use ordering blocks of up to \iota elements in the reduction | Adapted reduction for \iota-tight programs · \iota-tight ASP consistency | runtime lower bound: 2^{o(k\cdot\log(\iota))}\cdot\poly(\Card{\text{\normalfont at}(\Pi)}) | Hurt |
| Reduce SAT to normal ASP in subexponential time | SAT-to-normal ASP reduction · SAT formulas with treewidth k | minimum achievable treewidth: o(\frac{k}{\log(k)}) | No clear effect |
Closest papers by meaning
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.92)
- Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard (AAAI 2021 · similarity 0.91)
- Exact ASP Counting with Compact Encodings (AAAI 2024 · similarity 0.83)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.81)
- A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming (AAAI 2024 · similarity 0.81)
- SAT-Based Tree Decomposition with Iterative Cascading Policy Selection (AAAI 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.