ECCC-Report TR24-117https://eccc.weizmann.ac.il/report/2024/117Comments and Revisions published for TR24-117en-usSun, 14 Jul 2024 00:41:30 +0300
Paper TR24-117
| Partial Minimum Branching Program Size Problem is ETH-hard |
Ludmila Glinskih,
Artur Riazanov
https://eccc.weizmann.ac.il/report/2024/117We 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 our recent result (Glinskih and Riazanov, LATIN 2022) 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.Sun, 14 Jul 2024 00:41:30 +0300https://eccc.weizmann.ac.il/report/2024/117