# Time complexity of minimizing Boolean expression

Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used.

The following Wikipedia article only talks about the space complexity of the problem (which is PSPACE), but does not talks about the time complexity.

https://en.wikipedia.org/wiki/Circuit_minimization_for_Boolean_functions

• I couldn't find PSPACE in the article. Oct 6 '15 at 5:07
• It says that it is in in PH, which is a subset of PSPACE problem. Oct 6 '15 at 5:09
• I also couldn't find PH in the article. I could only find $\Sigma_2^P$. Oct 6 '15 at 5:10
• So does $\sum^P_2$-complete problem implies that it is a NPC/ NPH problem? Oct 6 '15 at 5:12
• I suggest you spend a few hours reading on the polynomial hierarchy. Oct 6 '15 at 5:14

The Wikipedia article states that the problem is $\Sigma_2^P$-hard, and in particular it's NP-hard. Therefore it's probably not solvable in polynomial time (unless P=NP).
• @jcod0, Wikipedia says that it's $\Sigma_2^P$-hard. It follows that it is NP-hard.