# 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. – Yuval Filmus Oct 6 '15 at 5:07
• It says that it is in in PH, which is a subset of PSPACE problem. – jcod0 Oct 6 '15 at 5:09
• I also couldn't find PH in the article. I could only find $\Sigma_2^P$. – Yuval Filmus Oct 6 '15 at 5:10
• So does $\sum^P_2$-complete problem implies that it is a NPC/ NPH problem? – jcod0 Oct 6 '15 at 5:12
• I suggest you spend a few hours reading on the polynomial hierarchy. – Yuval Filmus 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. – D.W. Oct 6 '15 at 5:13