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.


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

| cite | improve this answer | |
  • $\begingroup$ The Wikipedia article does not says that it is an NP-hard problem. If that is the case someone would have mapped a known NPC problem to the given problem. $\endgroup$ – jcod0 Oct 6 '15 at 5:11
  • $\begingroup$ @jcod0, Wikipedia says that it's $\Sigma_2^P$-hard. It follows that it is NP-hard. $\endgroup$ – D.W. Oct 6 '15 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.