285 research outputs found
Investigations Concerning the Structure of Complete Sets
No full textThis paper will discuss developments bearing on three related research directions where Somenath Biswas has made pioneering contributions:
• Isomorphism of Complete Sets
• Creative Sets
• Universal Relations
Some open questions in each of these directions will be highlighted.In series: Progress in Computer Science and Applied Logic (26)Peer reviewe
The Complexity of Complexity
No full textGiven a string, what is its complexity? We survey what is known about the computational complexity of this problem, and describe several open questions.Peer reviewedLecture Notes in Computer Science, Volume 10010
The new complexity landscape around circuit minimization
No full textWe survey recent developments related to the Minimum Circuit Size Problem
New insights on the (non-)hardness of circuit minimization and related problems
No full textThe 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-b^ounded Kolmogorov complexity) within a factor of n^{1−o(1)} is indeed NPintermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function. Our technique is quite general; we use it also to show that approximating the size of the largest clique in a graph within a factor of n^{1−o(1)} is also NP-intermediate unless NP ⊆ P/poly.
We also prove that MKTP is hard for the complexity class DET under non-uniform NC0 reductions. This
is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of “local” reductions such as NC0 reductions . We exploit this local reduction to obtain several new consequences:
—MKTP is not in AC0[p].
—Circuit size lower bounds are equivalent to hardness of a relativized version MKTP^A of MKTP under a class of uniform AC0 reductions, for a significant class of sets A.
—Hardness of MCSP^A implies hardness of MKTP^A for a significant class of sets A. This is the first result directly relating the complexity of MCSP^A and MKTP^A, for any A.Peer reviewed© ACM, 2019. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Computation Theory (TOCT), {Vol.11, Iss.4, (September 2019)} http://doi.acm.org/10.1145/3349616
Zero Knowledge and Circuit Minimization
No full textWe show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP MCSP.
This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP-intermediate problems.Peer reviewe
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
No full textWe show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC1 = Log(CFL)) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.Licensed under a Creative Commons Attribution License (CC-BY) http://creativecommons.org/licenses/by/3.0/Peer reviewe
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
No full textThe 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 n1−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 NC0 reductions.
This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of “local” reductions such as NC0-many-one reductions. We exploit this local reduction to obtain several new consequences:
* MKTP is not in AC0[p].
* Circuit size lower bounds are equivalent to hardness of a relativized version MKTPA of MKTP under a class of uniform AC0 reductions, for a large class of sets A.
* Hardness of MCSPA implies hardness of MKTPA for a wide class of sets A. This is the first result directly relating the complexity of MCSPA and MKTPA, for any A.Paper presented at the 42nd International Symposium on Mathematical Foundations of Computer Science, August 21-25, 2017, Aalborg, Denmark. This is the Author’s Original, a longer and more complete version of the paper published in: Larsen, K.G., Bodlaender, H.L., & Raskin, J.-F. (Eds.). (2017). Proceedings from 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. (Leibniz International Proceedings in Informatics (LIPIcs)). DOI: 10.4230/LIPIcs.MFCS.2017.54.Peer reviewed
Ker-I Ko and the study of resource-bounded Kolmogorov complexity
No full textKer-I Ko was among the first people to recognize the importance of resource-bounded Kolmogorov complexity as a tool for better understanding the structure of complexity classes. In this brief informal reminiscence, I review the milieu of the early 1980’s that caused an up-welling of interest in resource-bounded Kolmogorov complexity, and then I discuss some more recent work that sheds additional light on the questions related to Kolmogorov complexity that Ko grappled with in the 1980’s and 1990’s.
In particular, I include a detailed discussion of Ko’s work on the question of whether it is NP-hard to determine the time-bounded Kolmogorov complexity of a given string. This problem is closely connected with the Minimum Circuit Size Problem (MCSP), which is central to several contemporary investigations in computational complexity theory.Peer reviewe
On the Power of Algebraic Branching Programs of Width Two
No full textWe show that there are families of polynomials having small depth two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings.Peer reviewe
Zero Knowledge and Circuit Minimization
No full textWe show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RPMCSP.
This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the
long history these problems share, as candidate NP-intermediate problemsPeer reviewe
- …
