Minimum circuit size, graph isomorphism, and related problems. (English) Zbl 1397.68082
Summary: We study the computational power of deciding whether a given truth table can be described by a circuit of a given size (the minimum circuit size problem, or MCSP for short) and of the variant denoted as MKTP, where circuit size is replaced by a polynomially related Kolmogorov measure. Prior to our work, all reductions from supposedly intractable problems to MCSP/MKTP hinged on the power of MCSP/MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of graph isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include linear code equivalence, permutation group conjugacy, and matrix subspace conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
MSC:
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
Keywords:
reductions between NP-intermediate problems; graph isomorphism; minimum circuit size problem; time-bounded Kolmogorov complexityReferences:
| [1] | E. Allender, H. Buhrman, M. Koucký, D. van Melkebeek, and D. Ronneburger, Power from random strings, SIAM J. Comput., 35 (2006), pp. 1467–1493, . · Zbl 1106.68049 |
| [2] | E. Allender and B. Das, Zero knowledge and circuit minimization, Inform. and Comput., 256 (2017), pp. 2–8, . · Zbl 1376.68056 |
| [3] | E. Allender, J. A. Grochow, D. van Melkebeek, C. Moore, and A. Morgan, Minimum circuit size, graph isomorphism, and related problems, in 9th Innovations in Theoretical Computer Science Conference (ITCS ’18), LIPIcs. Leibniz Int. Proc. Inform. 94, A. R. Karlin, ed., Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, pp. 20:1–20:20, . · Zbl 1397.68082 |
| [4] | E. Allender and S. Hirahara, New insights on the (non)-hardness of circuit minimization and related problems, in 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), LIPIcs. Leibniz Int. Proc. Inform. 83, K. G. Larsen, H. L. Bodlaender, and J.-F. Raskin, eds., Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 54:1–54:14, . · Zbl 1441.68082 |
| [5] | E. Allender, M. Koucký, D. Ronneburger, and S. Roy, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, J. Comput. System Sci., 77 (2010), pp. 14–40, . · Zbl 1235.68085 |
| [6] | V. Arvind and P. P. Kurur, Graph isomorphism is in SPP, Inform. and Comput., 204 (2006), pp. 835–852, . · Zbl 1110.68090 |
| [7] | L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC ’91), New Orleans, LA, 1991, pp. 164–174, . |
| [8] | L. Babai, Graph isomorphism in quasipolynomial time, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC ’16), Cambridge, MA, 2016, pp. 684–697, . · Zbl 1376.68058 |
| [9] | L. Babai, personal communication, 2016. |
| [10] | L. Babai, R. Beals, and Á. Seress, Polynomial-time theory of matrix groups, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC ’09), Bethesda, MD, 2009, pp. 55–64, . · Zbl 1304.68065 |
| [11] | L. Babai, P. Codenotti, and Y. Qiao, Polynomial-time isomorphism test for groups with no abelian normal subgroups, in Automata, Languages, and Programming (ICALP ’12), Lecture Notes in Comput. Sci. 7391, A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer, eds., Springer, Berlin, Heidelberg, 2012, pp. 51–62, . · Zbl 1272.68475 |
| [12] | A. Blass and Y. Gurevich, Equivalence relations, invariants, and normal forms, SIAM J. Comput., 13 (1984), pp. 682–689, . · Zbl 0545.68035 |
| [13] | A. Blass and Y. Gurevich, Equivalence relations, invariants, and normal forms. II, in Logic and Machines: Decision Problems and Complexity (Münster, 1983), Lecture Notes in Comput. Sci. 171, E. Börger, G. Hasenjaeger, D. Rödding, eds., Springer, Berlin, 1984, pp. 24–42, . · Zbl 0545.68036 |
| [14] | M. Carmosino, R. Impagliazzo, V. Kabanets, and A. Kolokolova, Learning algorithms from natural proofs, in 31st Conference on Computational Complexity (CCC 2016), LIPIcs. Leibniz Int. Proc. Inform. 50, R. Raz, ed., Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, pp. 10:1–10:24, . · Zbl 1380.68242 |
| [15] | J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. System Sci., 18 (1979), pp. 143–154, . · Zbl 0412.68090 |
| [16] | P. Erdös and A. Rényi, Probabilistic methods in group theory, J. Anal. Math., 14 (1965), pp. 127–138, . · Zbl 0247.20045 |
| [17] | J. Finkelstein and B. Hescott, Polynomial-Time Kernel Reductions, \arXiv1604.08558cs.CC, 2016. |
| [18] | L. Fortnow and J. A. Grochow, Complexity classes of equivalence problems revisited, Inform. and Comput., 209 (2011), pp. 748–763, . · Zbl 1238.68061 |
| [19] | G. S. Frandsen and P. B. Miltersen, Reviewing bounds on the circuit size of the hardest functions, Inform. Process. Lett., 95 (2005), pp. 354–357, . · Zbl 1185.68358 |
| [20] | O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems, J. ACM, 38 (1991), pp. 691–729, . · Zbl 0799.68101 |
| [21] | O. Goldreich, A. Sahai, and S. Vadhan, Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK, in Advances in Cryptology — CRYPTO ’99, Lecture Notes in Comput. Sci. 1666, M. Wiener, ed., Springer, Berlin, Heidelberg, 1999, pp. 467–484, . · Zbl 0942.68046 |
| [22] | O. Goldreich and S. Vadhan, Comparing entropies in statistical zero knowledge with applications to the structure of SZK, in Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC ’99), IEEE, 1999, pp. 54–73, . |
| [23] | O. Goldreich and S. Vadhan, On the complexity of computational problems regarding distributions, in Studies in Complexity and Cryptography – Miscellanea on the Interplay Between Randomness and Computation, Lecture Notes in Comput. Sci. 6650, O. Goldreich, ed., Springer, Berlin, Heidelberg, 2011, pp. 13–29, . |
| [24] | O. Goldreich and S. Vadhan, personal communication, 2017. |
| [25] | J. A. Grochow, Matrix Lie algebra isomorphism, in Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC ’12), IEEE, 2012, pp. 203–213, . |
| [26] | J. H\aastad, R. Impagliazzo, L. Levin, and M. Luby, A pseudorandom generator from any one-way function, SIAM J. Comput., 28 (1999), pp. 1364–1396, . · Zbl 0940.68048 |
| [27] | S. Hirahara and R. Santhanam, On the average-case complexity of MCSP and its variants, in 32nd Computational Complexity Conference (CCC 2017), LIPIcs. Leibniz Int. Proc. Inform. 79, R. O’Donnell, ed., Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 7:1–7:20, . · Zbl 1435.68089 |
| [28] | S. Hirahara and O. Watanabe, Limits of minimum circuit size problem as oracle, in 31st Conference on Computational Complexity (CCC 2016), LIPIcs. Leibniz Int. Proc. Inform. 50, R. Raz, ed., Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, pp. 18:1–18:20, . · Zbl 1380.68240 |
| [29] | D. F. Holt, B. Eick, and E. A. O’Brien, Handbook of Computational Group Theory, Discrete Math. Appl., Chapman & Hall/CRC, Boca Raton, 2005. · Zbl 1091.20001 |
| [30] | V. Kabanets and J.-Y. Cai, Circuit minimization problem, in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC ’00), Portland, OR, 2000, pp. 73–79, . · Zbl 1296.94182 |
| [31] | W. M. Kantor and K. Magaard, Black box exceptional groups of Lie type, Trans. Amer. Math. Soc., 365 (2013), pp. 4895–4931, . · Zbl 1285.20012 |
| [32] | W. M. Kantor and K. Magaard, Black box exceptional groups of Lie type II, J. Algebra, 421 (2015), pp. 524–540, . · Zbl 1304.20020 |
| [33] | D. E. Knuth, The Art of Computer Programming, Sorting and Searching 3, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010 |
| [34] | J. Köbler, U. Schöning, and J. Torán, The Graph Isomorphism Problem: Its Structural Complexity, Birkhauser Verlag, Basel, Switzerland, 1993, . · Zbl 0813.68103 |
| [35] | M. W. Liebeck and E. A. O’Brien, Recognition of finite exceptional groups of Lie type, Trans. Amer. Math. Soc., 368 (2016), pp. 6189–6226, . · Zbl 1345.20065 |
| [36] | C. D. Murray and R. R. Williams, On the (non) NP-hardness of computing circuit complexity, Theory Comput., 13 (2017), pp. 1–22, . · Zbl 1378.68053 |
| [37] | N. Nisan and A. Wigderson, Hardness vs randomness, J. Comput. Syst. Sci. Int., 49 (1994), pp. 149–167, . · Zbl 0821.68057 |
| [38] | I. C. C. Oliveira and R. Santhanam, Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness, in 32nd Computational Complexity Conference (CCC 2017), LIPIcs. Leibniz Int. Proc. Inform. 79, R. O’Donnell, ed., Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 18:1–18:49, . · Zbl 1440.68083 |
| [39] | R. Paturi and P. Pudlák, On the complexity of circuit satisfiability, in Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC ’10), Cambridge, MA, 2010, pp. 241–250, . · Zbl 1293.68173 |
| [40] | E. Petrank and R. M. Roth, Is code equivalence easy to decide?, IEEE Trans. Inform. Theory, 43 (1997), pp. 1602–1604, . · Zbl 0884.94025 |
| [41] | M. Rudow, Discrete logarithm and minimum circuit size, Inform. Process. Lett., 128 (2017), pp. 1–4, . · Zbl 1422.68141 |
| [42] | A. Sahai and S. Vadhan, A complete problem for statistical zero knowledge, J. ACM, 50 (2003), pp. 196–249, . · Zbl 1326.68165 |
| [43] | A. Seress, Permutation Group Algorithms, Cambridge Tracts in Math. 152, Cambridge University Press, Cambridge, 2003, . · Zbl 1028.20002 |
| [44] | B. A. Trakhtenbrot, A survey of Russian approaches to perebor (brute-force searches) algorithms, IEEE Ann. Hist. Comput., 6 (1984), pp. 384–400, . · Zbl 0998.01527 |
| [45] | M. Yamamoto, A Tighter Lower Bound on the Circuit Size of the Hardest Boolean Functions, Technical Report TR11-086, Electronic Colloquium on Computational Complexity, 2011. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
