NP-hardness of minimum circuit size problem for OR-AND-MOD circuits
The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have demonstrated the central...
| Автори: | , , |
|---|---|
| Формат: | Conference item |
| Опубліковано: |
Schloss Dagstuhl
2018
|
| _version_ | 1826301328960258048 |
|---|---|
| author | Hirahara, S Oliveira, I Santhanam, R |
| author_facet | Hirahara, S Oliveira, I Santhanam, R |
| author_sort | Hirahara, S |
| collection | OXFORD |
| description | The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have demonstrated the central role of this problem and its variations in diverse areas such as cryptography, derandomization, proof complexity, learning theory, and circuit lower bounds. <br/> <p>The NP-hardness of computing the minimum numbers of terms in a DNF formula consistent with a given truth table was proved by W. Masek [31] in 1979. In this work, we make the first progress in showing NP-hardness for more expressive classes of circuits, and establish an analogous result for the MCSP problem for depth-3 circuits of the form OR-AND-MOD2. Our techniques extend to an NP-hardness result for MODm 25 gates at the bottom layer under inputs from (Z/mZ)n.</p> |
| first_indexed | 2024-03-07T05:30:45Z |
| format | Conference item |
| id | oxford-uuid:e231576d-a5f0-4119-bc1d-5aa8ef2a046f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:30:45Z |
| publishDate | 2018 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:e231576d-a5f0-4119-bc1d-5aa8ef2a046f2022-03-27T09:59:26ZNP-hardness of minimum circuit size problem for OR-AND-MOD circuitsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e231576d-a5f0-4119-bc1d-5aa8ef2a046fSymplectic Elements at OxfordSchloss Dagstuhl2018Hirahara, SOliveira, ISanthanam, RThe Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have demonstrated the central role of this problem and its variations in diverse areas such as cryptography, derandomization, proof complexity, learning theory, and circuit lower bounds. <br/> <p>The NP-hardness of computing the minimum numbers of terms in a DNF formula consistent with a given truth table was proved by W. Masek [31] in 1979. In this work, we make the first progress in showing NP-hardness for more expressive classes of circuits, and establish an analogous result for the MCSP problem for depth-3 circuits of the form OR-AND-MOD2. Our techniques extend to an NP-hardness result for MODm 25 gates at the bottom layer under inputs from (Z/mZ)n.</p> |
| spellingShingle | Hirahara, S Oliveira, I Santhanam, R NP-hardness of minimum circuit size problem for OR-AND-MOD circuits |
| title | NP-hardness of minimum circuit size problem for OR-AND-MOD circuits |
| title_full | NP-hardness of minimum circuit size problem for OR-AND-MOD circuits |
| title_fullStr | NP-hardness of minimum circuit size problem for OR-AND-MOD circuits |
| title_full_unstemmed | NP-hardness of minimum circuit size problem for OR-AND-MOD circuits |
| title_short | NP-hardness of minimum circuit size problem for OR-AND-MOD circuits |
| title_sort | np hardness of minimum circuit size problem for or and mod circuits |
| work_keys_str_mv | AT hiraharas nphardnessofminimumcircuitsizeproblemfororandmodcircuits AT oliveirai nphardnessofminimumcircuitsizeproblemfororandmodcircuits AT santhanamr nphardnessofminimumcircuitsizeproblemfororandmodcircuits |