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
|