A Boolean formula is minimal if there is no shorter Boolean formula that is equivalent to . Let MIN-FORMULA = { | is a minimal formula }. (a) Show...

A Boolean formula is minimal if there is no shorter Boolean formula that is equivalent to . Let MIN-FORMULA = { | is a minimal formula }. (a) Show that MIN-FORMULA (b) PSPACE. Explain why the following argument fails to show that MIN-FORMULA co-NP: If MIN-FORMULA, then has a smaller equivalent formula. A nondeterministic / Turing Machine can verify that MIN-FORMULA by guessing that formula