  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.
