A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916737543307264 |
|---|---|
| author | Lagerkvist, Victor Maizia, Mohamed Schmidt, Johannes |
| author_facet | Lagerkvist, Victor Maizia, Mohamed Schmidt, Johannes |
| contents | The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for $Σ^P_2$- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a $Σ^P_2$-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10201 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds Lagerkvist, Victor Maizia, Mohamed Schmidt, Johannes Computational Complexity Artificial Intelligence F.2.2 The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for $Σ^P_2$- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a $Σ^P_2$-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis. |
| title | A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds |
| topic | Computational Complexity Artificial Intelligence F.2.2 |
| url | https://arxiv.org/abs/2505.10201 |