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$ 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$ 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$ 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).

  • $\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.