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.MFCS.2017.54
URN: urn:nbn:de:0030-drops-80636
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8063/
Go to the corresponding LIPIcs Volume Portal

Allender, Eric ; Hirahara, Shuichi

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

pdf-format:
LIPIcs-MFCS-2017-54.pdf (0.5 MB)

Abstract

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of n^{1 - o(1)} is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function.

We also prove that MKTP is hard for the complexity class DET under
non-uniform NC^0 reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of "local" reductions such as NC^0 reductions. We exploit this local reduction to obtain several new consequences:

* MKTP is not in AC^0[p].

* Circuit size lower bounds are equivalent to hardness of a relativized version MKTP^A of MKTP under a class of uniform AC^0 reductions, for a large class of sets A.

* Hardness of MCSP^A implies hardness of MKTP^A for a wide class of
sets A. This is the first result directly relating the complexity of
MCSP^A and MKTP^A, for any A.

BibTeX - Entry

@InProceedings{allender_et_al:LIPIcs:2017:8063,
  author =	{Eric Allender and Shuichi Hirahara},
  title =	{{New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8063},
  URN =		{urn:nbn:de:0030-drops-80636},
  doi =		{10.4230/LIPIcs.MFCS.2017.54},
  annote =	{Keywords: computational complexity, Kolmogorov complexity, circuit size}
}

Keywords: computational complexity, Kolmogorov complexity, circuit size
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

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