Ilango, Rahul ;
Loff, Bruno ;
Oliveira, Igor C.
NPHardness of Circuit Minimization for MultiOutput Functions
Abstract
Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NPcomplete. While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive.
In this work, we establish the first NPhardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits. More precisely, we show that computing the minimum circuit size of a given multioutput Boolean function f : {0,1}^n → {0,1}^m is NPhard under manyone polynomialtime randomized reductions. Our argument builds on a simpler NPhardness proof for the circuit minimization problem for (singleoutput) Boolean functions under an extended set of generators.
Complementing these results, we investigate the computational hardness of minimizing communication. We establish that several variants of this problem are NPhard under deterministic reductions. In particular, unless 𝖯 = 𝖭𝖯, no polynomialtime computable function can approximate the deterministic twoparty communication complexity of a partial Boolean function up to a polynomial. This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions.
BibTeX  Entry
@InProceedings{ilango_et_al:LIPIcs:2020:12574,
author = {Rahul Ilango and Bruno Loff and Igor C. Oliveira},
title = {{NPHardness of Circuit Minimization for MultiOutput Functions}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {22:122:36},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12574},
URN = {urn:nbn:de:0030drops125744},
doi = {10.4230/LIPIcs.CCC.2020.22},
annote = {Keywords: MCSP, circuit minimization, communication complexity, Boolean circuit}
}
17.07.2020
Keywords: 

MCSP, circuit minimization, communication complexity, Boolean circuit 
Seminar: 

35th Computational Complexity Conference (CCC 2020)

Issue date: 

2020 
Date of publication: 

17.07.2020 