\footnotesize
    \leavevmode\renewcommand{\arraystretch}{1.3}
    \begin{tabular}{l|llllll}
   Representation of     &          & \multicolumn2c{test for}  &
   \multicolumn{3}c{boolean operations} \\
   boolean functions      & compact? & satisf'ty& validity &
   \multicolumn1c{$\cdot$} & \multicolumn1c{$+$} &
\multicolumn1c{$\bar{\ }$} \\\hline
%
   Prop.\ formulas       &  often   &  hard    & hard   &  easy & easy &
easy\\
   Formulas in DNF       & sometimes&  easy    & hard   &  hard & easy &
hard\\
   Formulas in CNF       & sometimes&  hard    & easy   &  easy & hard &
hard\\
   Ordered truth tables  &  never   &  hard    & hard   &  hard & hard &
hard\\
   Reduced OBDDs         &  often   &  easy    & easy   &  medium &
medium & easy\\
\end{tabular}