How to encode a logical structure by an OBDD
H. Veith · 2002
The complexity of problems whose instances are represented by ordered binary decision diagrams (OBDDs) is investigated. By using interleaved variable orders which are well-known in symbolic model checking, we derive hardness results for OBDDs from a Conversion Lemma, extending previous related work about succinct circuit problems and succinct formula problems. This method is applicable for all problems which are complete under Immerman's quantifier free reductions, in particular the problems investigated previously.