TOPICS
Search

Minimum Equivalent Expression

The minimum equivalent expression problem asks whether a given sentential formula has an equivalent formula of size at most k over the same variables. The basis consists of AND, OR, and NOT, truth constants are allowed, and size is the number of variable occurrences (Jaakkola 2026).

Buchfuhrer and Umans (2011) established Sigma_2^p-completeness under Turing reductions. Jaakkola (2026) strengthened this to completeness under polynomial-time many-one reductions. The class Sigma_2^p consists of decision problems whose membership can be expressed by a polynomial-time predicate with a polynomially bounded existential certificate followed by a polynomially bounded universal certificate. Jaakkola (2026) attributes the central proof to AI-generated arguments.

See also

Propositional Calculus

Explore with Wolfram|Alpha

References

Buchfuhrer, D. and Umans, C. "The Complexity of Boolean Formula Minimization." J. Comput. System Sci. 77, 142-153, 2011. https://doi.org/10.1016/j.jcss.2010.06.011.Jaakkola, R. "Propositional Formula Minimization Is Sigma_2^p-Complete under Many-One Reductions." 25 Oct 2026. https://arxiv.org/abs/2610.34516.

Cite this as:

Weisstein, Eric W. "Minimum Equivalent Expression." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MinimumEquivalentExpression.html

Subject classifications