The complexity of Boolean formula minimization

Allender, 2008, Minimizing disjunctive normal form formulas and AC0 circuits given a truth table, SIAM J. Comput., 38, 63, 10.1137/060664537 Allender, 2010, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, J. Comput. System Sci., 77, 14, 10.1016/j.jcss.2010.06.004 Allender, 2003, Derandomization and distinguishing complexity, 209 Devadas, 1994 Garey, 1979 E. Hemaspaandra, G. Wechsung. The minimization problem for Boolean formulas, in: FOCS, 1997, pp. 575–584. Hemaspaandra, 2002, The minimization problem for boolean formulas, SIAM J. Comput., 31, 1948, 10.1137/S0097539799362639 V. Kabanets, J.-Y. Cai, Circuit minimization problem, in: STOC, 2000, pp. 73–79. A.R. Meyer, L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, in: FOCS, IEEE, 1972, pp. 125–129. Papadimitriou, 1994, Computational Stockmeyer, 1976, The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1, 10.1016/0304-3975(76)90061-X Schaefer C. Umans, The minimum equivalent DNF problem and shortest implicants, in: FOCS, 1998, pp. 556–563. C. Umans, Hardness of approximating Σ2P minimization problems, in: FOCS, 1999, pp. 465–474. Umans, 2001, The minimum equivalent DNF problem and shortest implicants, J. Comput. System Sci., 63, 597, 10.1006/jcss.2001.1775 Umans, 2006, Complexity of two-level logic minimization, IEEE Trans. CAD Integr. Circuits Syst., 25, 1230, 10.1109/TCAD.2005.855944