2025/11/21 by Carmosino, Marco, Dang, Ngu, Jackman, Tim
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.16903
The Minimum Circuit Size Problem for Partial Functions (MCSP^*) is hard assuming the Exponential Time Hypothesis (ETH) (Ilango, 2020). This breakthrough hardness result leveraged a characterization of the optimal \∧, ∨, ¬\ circuits for n-bit OR (ORn) and a reduction from the partial f-Simple Extension Problem where f = ORn. It remains open to extend that reduction to show ETH-hardness of total MCSP. However, Ilango observed that the total f-Simple Extension Problem is easy whenever f is computed by read-once formulas (like ORn). Therefore, extending Ilango's proof to total MCSP would require one to replace ORn with a slightly more complex but similarly well-understood Boolean function. This work shows that the f-Simple Extension problem remains easy when f is the next natural candidate: XORn. We first develop a fixed-parameter tractable algorithm for the f-Simple Extension Problem that is efficient whenever the optimal circuits for f are (1) linear in size, (2) polynomially "few" and efficiently enumerable in the truth-table size (up to isomorphism and permutation of inputs), and (3) all have constant bounded fan-out. XORn satisfies all three of these conditions. When ¬ gates count towards circuit size, optimal XORn circuits are binary trees of n-1 subcircuits computing (¬)XOR2 (Kombarov, 2011). We extend this characterization when ¬ gates do not contribute the circuit size. Thus, the XOR-Simple Extension Problem is in polynomial time under both measures of circuit complexity.