License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.5
URN: urn:nbn:de:0030-drops-88831
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8883/
Go to the corresponding LIPIcs Volume Portal

Hirahara, Shuichi ; Oliveira, Igor C. ; Santhanam, Rahul

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

pdf-format:
LIPIcs-CCC-2018-5.pdf (0.7 MB)

Abstract

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.
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 [William J. Masek, 1979] 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-MOD_2. Our techniques extend to an NP-hardness result for MOD_m gates at the bottom layer under inputs from (Z / m Z)^n.

BibTeX - Entry

@InProceedings{hirahara_et_al:LIPIcs:2018:8883,
  author =	{Shuichi Hirahara and Igor C. Oliveira and Rahul Santhanam},
  title =	{{NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{5:1--5:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8883},
  URN =		{urn:nbn:de:0030-drops-88831},
  doi =		{10.4230/LIPIcs.CCC.2018.5},
  annote =	{Keywords: NP-hardness, Minimum Circuit Size Problem, depth-3 circuits}
}

Keywords: NP-hardness, Minimum Circuit Size Problem, depth-3 circuits
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI