Partial Minimum Branching Program Size Problem is ETH-hard
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929410634940416 |
|---|---|
| author | Glinskih, Ludmila Riazanov, Artur |
| author_facet | Glinskih, Ludmila Riazanov, Artur |
| contents | We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-k branching programs and OBDDs.
Combining these results with the recent unconditional lower bounds for MCSP [Glinskih, Riazanov'22], we obtain an unconditional superpolynomial lower bound on the size of Read-Once Nondeterministic Branching Programs (1-NBP) computing the total versions of the minimum BP, read-k-BP, and OBDD size problems.
Additionally we show that it is NP-hard to check whether a given BP computing a partial Boolean function can be compressed to a BP of a given size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04632 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partial Minimum Branching Program Size Problem is ETH-hard Glinskih, Ludmila Riazanov, Artur Computational Complexity We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-k branching programs and OBDDs. Combining these results with the recent unconditional lower bounds for MCSP [Glinskih, Riazanov'22], we obtain an unconditional superpolynomial lower bound on the size of Read-Once Nondeterministic Branching Programs (1-NBP) computing the total versions of the minimum BP, read-k-BP, and OBDD size problems. Additionally we show that it is NP-hard to check whether a given BP computing a partial Boolean function can be compressed to a BP of a given size. |
| title | Partial Minimum Branching Program Size Problem is ETH-hard |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2407.04632 |