Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.16903 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911278161723392 |
|---|---|
| author | Carmosino, Marco Dang, Ngu Jackman, Tim |
| author_facet | Carmosino, Marco Dang, Ngu Jackman, Tim |
| contents | 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 $\{\land, \lor, \neg\}$ circuits for $n$-bit $OR$ ($OR_n$) and a reduction from the partial $f$-Simple Extension Problem where $f = OR_n$. 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 $OR_n$). Therefore, extending Ilango's proof to total $MCSP$ would require one to replace $OR_n$ 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: $XOR_n$. 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. $XOR_n$ satisfies all three of these conditions. When $\neg$ gates count towards circuit size, optimal $XOR_n$ circuits are binary trees of $n-1$ subcircuits computing $(\neg)XOR_2$ (Kombarov, 2011). We extend this characterization when $\neg$ gates do not contribute the circuit size. Thus, the $XOR$-Simple Extension Problem is in polynomial time under both measures of circuit complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simple Circuit Extensions for XOR in PTIME Carmosino, Marco Dang, Ngu Jackman, Tim Computational Complexity 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 $\{\land, \lor, \neg\}$ circuits for $n$-bit $OR$ ($OR_n$) and a reduction from the partial $f$-Simple Extension Problem where $f = OR_n$. 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 $OR_n$). Therefore, extending Ilango's proof to total $MCSP$ would require one to replace $OR_n$ 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: $XOR_n$. 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. $XOR_n$ satisfies all three of these conditions. When $\neg$ gates count towards circuit size, optimal $XOR_n$ circuits are binary trees of $n-1$ subcircuits computing $(\neg)XOR_2$ (Kombarov, 2011). We extend this characterization when $\neg$ gates do not contribute the circuit size. Thus, the $XOR$-Simple Extension Problem is in polynomial time under both measures of circuit complexity. |
| title | Simple Circuit Extensions for XOR in PTIME |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.16903 |