Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-117 | 12th June 2024 18:18

Partial Minimum Branching Program Size Problem is ETH-hard

RSS-Feed




TR24-117
Authors: Ludmila Glinskih, Artur Riazanov
Publication: 14th July 2024 00:41
Downloads: 143
Keywords: 


Abstract:

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 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.



ISSN 1433-8092 | Imprint