Source-linked AI summary
Propositional formula minimization is $\Sigma_2^p$-complete under many-one reductions
Reijo Jaakkola
TL;DR
MEE asks whether a propositional formula has an equivalent formula with at most a specified number of variable occurrences, a question whose many-one completeness remained unresolved. The paper modifies a reduction from Succinct Set Cover to write its threshold explicitly, proving MEE Σp 2-complete under polynomial-time many-one reductions.
Problem
MEE’s Σp 2-completeness under polynomial-time many-one reductions remained open, despite an earlier polynomial-time Turing-reduction completeness result.
Source: §1 · p. 1Method
The proof modifies the Succinct Set Cover reduction by making the final MEE threshold explicit, avoiding oracle calls.
Source: §1 · p. 1Results
MEE is Σp 2-complete under polynomial-time many-one reductions.
Source: §1 · p. 1Takeaways & Limitations
The paper resolves the many-one completeness question for MEE.
Source: §1 · p. 1The proof uses a size convention under which formulas may be assumed without loss of generality to be in negation normal form.
Source: §2 · p. 2
Abstract
from arXiv · showhide
The Minimum Equivalent Expression problem (MEE) asks, given a propositional formula $\phi$ and an integer $k$, whether $\phi$ is equivalent to a formula with at most $k$ occurrences of propositional variables. While the problem is clearly in $\Sigma_2^p$, its completeness under polynomial-time many-one reductions has remained open since at least 1979. Buchfuhrer and Umans showed in 2008 that it is $\Sigma_2^p$-complete under polynomial-time Turing reductions. In this note, we present a proof discovered by GPT-Sol-6.1 which establishes that MEE is $\Sigma_2^p$-complete also under polynomial-time many-one reductions.
1 Introduction
MEE asks whether a propositional formula has an equivalent formula with at most a given number of variable occurrences. The paper resolves the long-standing question of many-one completeness by making the reduction threshold explicit, and motivates the problem through faithful global explanations.
1 Introduction
- MEE was listed as open in 1979, and Buchfuhrer and Umans established Σp 2-completeness under polynomial-time Turing reductions in 2008.Hemaspaandra and Wechsung proved hardness under many-one reductions for problems solvable with parallel access to an NP oracle.Source: §1 · p. 1
- MEE is Σp 2-complete under polynomial-time many-one reductions, with an explicit threshold that removes oracle calls from the earlier Turing-reduction strategy.The reduction follows Buchfuhrer and Umans from Succinct Set Cover, introduced by Umans.Source: §1 · p. 1
- For a completely faithful global explanation of a formula represented as a classifier, an optimal explanation is a smallest equivalent formula, making the task precisely MEE.The paper measures formula size by the number of propositional-variable occurrences.Source: §1 · pp. 1–2
- The proof was discovered by GPT-Sol-6.1, then rewritten for clarity by Opus 5.5, with GPT-6 and Sonnet 5.5 assisting manuscript writing and editing.Source: §1 · p. 2
2 Preliminaries
The preliminaries specify propositional formulas and their semantics, then introduce a weighted formula-size measure. They also establish a negation-normal-form convention and a variable-replacement construction used later.
2 Preliminaries
- PL[Φ] consists of Boolean formulas over Φ generated from constants and variables using negation, conjunction, and disjunction.Source: §2 · p. 2
- A Φ-assignment maps variables to Boolean values, and equivalence means that two formulas entail each other.Source: §2 · p. 2
- The weighted size sizew(ϕ) assigns weights to proposition symbols and is defined recursively; constant-one weights yield the ordinary size notation.Source: §2 · p. 2
- With this size convention, formulas may be assumed without loss of generality to be in negation normal form, where negation applies only to variables.Source: §2 · p. 2
- The construction ϕw replaces each variable by a conjunction of fresh variables, reusing its block across occurrences and assigning disjoint blocks to distinct variables.The cited lemma is described as essentially proved in.Source: §2 · p. 3
3 Main result
The paper proves MEE Σ_2^p-complete under polynomial-time many-one reductions and establishes this by modifying a reduction from Succinct Set Cover. Its two correctness directions connect small equivalent formulas with covers of size at most k.
3 Main result
- MEE is Σ_2^p-complete under polynomial-time many-one reductions.Source: §3 · p. 3
3.1 The reduction
- The reduction maps Succinct Set Cover to a weighted MEE instance, using variable weights to constrain equivalent formulas and recover a small cover.The output is (ϕw, K), computable in polynomial time.Source: §3.1 · pp. 3–4
3.3 Right to left direction
- Conversely, a bounded-size equivalent formula identifies at most k variables whose corresponding 3-DNF formulas form a cover.The size bound gives |J| ≤ k, and the proof shows J is a cover.Source: §3.3 · pp. 5–6