Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2501.03710 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914370622062592 |
|---|---|
| author | Calí, Andrea Razgon, Igor |
| author_facet | Calí, Andrea Razgon, Igor |
| contents | Decision \textsc{dnnf} (a.k.a. $\wedge_d$-\textsc{fbdd}) is an important special case of Decomposable Negation Normal Form (\textsc{dnnf}), a landmark knowledge compilation model. Like other known \textsc{dnnf} restrictions, Decision \textsc{dnnf} admits \textsc{fpt} sized representation of \textsc{cnf}s of bounded \emph{primal} treewidth. However, unlike other restrictions, the complexity of representation for \textsc{cnf}s of bounded \emph{incidence} treewidth is wide open.
In[arxiv:1708.07767], we resolved this question for two restricted classes of Decision \textsc{dnnf} that we name $\wedge_d$-\textsc{obdd} and Structured Decision \textsc{dnnf}. In particular, we demonstrated that, while both these classes have \textsc{fpt}-sized representations for \textsc{cnf}s of bounded primal treewidth, they need \textsc{xp}-size for representation of \textsc{cnf}s of bounded incidence treewidth.
In the main part of this paper we carry out an in-depth study of the $\wedge_d$-\textsc{obdd} model. We formulate a generic methodology for proving lower bounds for the model. Using this methodology, we reestablish the \textsc{xp} lower bound provided in [arxiv:1708.07767]. We also provide exponential separations between \textsc{fbdd} and $\wedge_d$-\textsc{obdd} and between $\wedge_d$-\textsc{obdd} and an ordinary \textsc{obdd}.
We study the complexity of Apply operation for $\wedge_d$-\textsc{obdd}. While, in general, the Apply operation leads to exponential blow up of the resulting model, we identify a special restricted case where the Apply operation can be carried out efficiently.
We introduce a relaxed version of Structured Decision \textsc{dnnf} that we name Structured $\wedge_d$-\textsc{fbdd} and demonstrate that this model is quite powerful for \textsc{cnf}s of bounded incidence treewidth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03710 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On complexity of restricted fragments of Decision DNNF Calí, Andrea Razgon, Igor Computational Complexity Decision \textsc{dnnf} (a.k.a. $\wedge_d$-\textsc{fbdd}) is an important special case of Decomposable Negation Normal Form (\textsc{dnnf}), a landmark knowledge compilation model. Like other known \textsc{dnnf} restrictions, Decision \textsc{dnnf} admits \textsc{fpt} sized representation of \textsc{cnf}s of bounded \emph{primal} treewidth. However, unlike other restrictions, the complexity of representation for \textsc{cnf}s of bounded \emph{incidence} treewidth is wide open. In[arxiv:1708.07767], we resolved this question for two restricted classes of Decision \textsc{dnnf} that we name $\wedge_d$-\textsc{obdd} and Structured Decision \textsc{dnnf}. In particular, we demonstrated that, while both these classes have \textsc{fpt}-sized representations for \textsc{cnf}s of bounded primal treewidth, they need \textsc{xp}-size for representation of \textsc{cnf}s of bounded incidence treewidth. In the main part of this paper we carry out an in-depth study of the $\wedge_d$-\textsc{obdd} model. We formulate a generic methodology for proving lower bounds for the model. Using this methodology, we reestablish the \textsc{xp} lower bound provided in [arxiv:1708.07767]. We also provide exponential separations between \textsc{fbdd} and $\wedge_d$-\textsc{obdd} and between $\wedge_d$-\textsc{obdd} and an ordinary \textsc{obdd}. We study the complexity of Apply operation for $\wedge_d$-\textsc{obdd}. While, in general, the Apply operation leads to exponential blow up of the resulting model, we identify a special restricted case where the Apply operation can be carried out efficiently. We introduce a relaxed version of Structured Decision \textsc{dnnf} that we name Structured $\wedge_d$-\textsc{fbdd} and demonstrate that this model is quite powerful for \textsc{cnf}s of bounded incidence treewidth. |
| title | On complexity of restricted fragments of Decision DNNF |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2501.03710 |