Before revision: For the case when the Boolean function is specified by a circuit (that is, we want to find an equivalent circuit of minimum size possible), the unbounded circuit minimization problem was long-conjectured to be -complete in time complexity (the complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time) , a result finally proved in 2008, but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.
After revision: For the case when the Boolean function is specified by a circuit (that is, we want to find an equivalent circuit of minimum size possible), the unbounded circuit minimization problem was long-conjectured to be -complete in time complexity , a result finally proved in 2008, but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.