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.2020.31
URN: urn:nbn:de:0030-drops-125834
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12583/
Go to the corresponding LIPIcs Volume Portal

Ilango, Rahul

Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas

pdf-format:
LIPIcs-CCC-2020-31.pdf (0.7 MB)

Abstract

A longstanding open question is whether there is an equivalence between the computational task of determining the minimum size of any circuit computing a given function and the task of producing a minimum-sized circuit for a given function. While it is widely conjectured that both tasks require "perebor," or brute-force search, researchers have not yet ruled out the possibility that the search problem requires exponential time but the decision problem has a linear time algorithm.
In this paper, we make progress in connecting the search and decision complexity of minimizing formulas. Let MFSP denote the problem that takes as input the truth table of a Boolean function f and an integer size parameter s and decides whether there is a formula for f of size at most s. Let Search- denote the corresponding search problem where one has to output some optimal formula for computing f.
Our main result is that given an oracle to MFSP, one can solve Search-MFSP in time polynomial in the length N of the truth table of f and the number t of "near-optimal" formulas for f, in particular O(N⁶t²)-time. While the quantity t is not well understood, we use this result (and some extensions) to prove that given an oracle to MFSP:
- there is a deterministic 2^O(N/(log log N))-time oracle algorithm for solving Search-MFSP on all but a o(1)-fraction of instances, and
- there is a randomized O(2^.67N)-time oracle algorithm for solving Search-MFSP on all instances. Intriguingly, the main idea behind our algorithms is in some sense a "reverse application" of the gate elimination technique.

BibTeX - Entry

@InProceedings{ilango:LIPIcs:2020:12583,
  author =	{Rahul Ilango},
  title =	{{Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{31:1--31:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12583},
  URN =		{urn:nbn:de:0030-drops-125834},
  doi =		{10.4230/LIPIcs.CCC.2020.31},
  annote =	{Keywords: minimum circuit size problem, minimum formula size problem, gate elimination, search to decision reduction, self-reducibility}
}

Keywords: minimum circuit size problem, minimum formula size problem, gate elimination, search to decision reduction, self-reducibility
Collection: 35th Computational Complexity Conference (CCC 2020)
Issue Date: 2020
Date of publication: 17.07.2020

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