Automating OBDD proofs is NP-hard.

Dmitry Itsykson, Artur Riazanov

Browse the full MFCS paper archive.