Time complexity of Boolean minimization.

This thesis deals with the time complexity of Boolean minimization - minimization of formulae that represent Boolean functions. It presents basic concepts from the area of Boolean functions, of their normal form representations and of minimization of these representations. A whole chapter is dedicated to Umans's [13] proofs of 2 completeness of minimization of general DNF formulae for both common measures of minimality. For a class of formulae called Matched this thesis presents new results that show that although satisfiability problem is easy for Matched formulae (difficult for an arbitrary formula), problems connected to minimization and minimization itself is as hard for Matched formulae as it is for general formulae