Top

Published in:

2020 | OriginalPaper | Chapter

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

Author : Eric Allender

Published in: Complexity and Approximation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Ker-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 \({\mathsf{NP}}\)-hard to determine the time-bounded Kolmogorov complexity of a given string. This problem is closely connected with the Minimum Circuit Size Problem (\({\mathsf{MCSP}}\)), which is central to several contemporary investigations in computational complexity theory.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter In Memoriam: Ker-I Ko (1950–2018)

next chapter The Power of Self-Reducibility: Selectivity, Information, and Approximation

If the reader is not familiar with Kolmogorov complexity, then we recommend some excellent books on this topic [25, 44].

Levin was Kolmogorov’s student, but he did not receive his Ph.D. until after he emigrated to the US, and Albert Meyer was his advisor at MIT. The circumstances around Levin being denied his Ph.D. in Moscow are described in the excellent article by Trakhtenbrot [59].

This result also appears as Exercise 13.20 in what was probably the most popular complexity theory textbook for the early 1980’s [33], which credits Levin for that result, but not for what is now called the Cook-Levin theorem.

In [1], in addition to Levin, Adleman also credits Meyer and McCreight [46] with developing similar ideas. I have been unable to detect any close similarity, although the final paragraph of [46] states “Our results are closely related to more general definitions of randomness proposed by Kolmogorov, Martin-Löf, and Chaitin” [and here the relevant literature is cited, before continuing] “A detailed discussion must be postponed because of space limitations” [and here Meyer and McCreight include a citation to a letter from the vice-president of Academic Press (which presumably communicated the space limitations to the authors).] Indeed, Meyer and McCreight were interested in when a decidable (and therefore very non-random) set can be said to “look random” and thereby deserve to be called pseudorandom. We will return to this topic later in the paper.

During the review and revision phase of preparing this paper, I was given a paper that settles this question! Ilango, Loff, and Oliveira have now shown that the “circuit” version of this problem (which they call \({\mathsf{Partial}\hbox {-}\mathsf{MCSP}}\)) is \({\mathsf{NP}}\)-complete [35]. For additional discussion of this result and how it contrasts with Ko’s work [38], see [4].

In particular, this is the problem that Trakhtenbrot calls “Task 5” in [59].

Adleman, L.M.: Time, space and randomness. Technical report, MIT/LCS/TM-131, MIT (1979)

Allender, E.: Some consequences of the existence of pseudorandom generators. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 151–159 (1987). https://doi.org/10.1145/28395.28412, see also [3]

Allender, E.: Some consequences of the existence of pseudorandom generators. J. Comput. Syst. Sci. 39(1), 101–124 (1989). https://doi.org/10.1016/0022-0000(89)90021-4MathSciNetCrossRefMATH

Allender, E.: The new complexity landscape around circuit minimization. In: Proceedings of the 14th International Conference on Language and Automata Theory and Applications (LATA) (2020, to appear)

Allender, E., Buhrman, H., Friedman, L., Loff, B.: Reductions to the set of random strings: the resource-bounded case. Logical Methods Comput. Sci. 10(3) (2014). https://doi.org/10.2168/LMCS-10(3:5)2014

Allender, E., Buhrman, H., Koucky, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35, 1467–1493 (2006). https://doi.org/10.1137/050628994MathSciNetCrossRefMATH

Allender, E., Das, B.: Zero knowledge and circuit minimization. Inf. Comput. 256, 2–8 (2017). https://doi.org/10.1016/j.ic.2017.04.004. Special issue for MFCS 2014MathSciNetCrossRefMATH

Allender, E., Grochow, J., van Melkebeek, D., Morgan, A., Moore, C.: Minimum circuit size, graph isomorphism and related problems. SIAM J. Comput. 47, 1339–1372 (2018). https://doi.org/10.1137/17M1157970MathSciNetCrossRefMATH

Allender, E., Hirahara, S.: New insights on the (non)-hardness of circuit minimization and related problems. ACM Trans. Comput. Theory (ToCT) 11(4), 27:1–27:27 (2019). https://doi.org/10.1145/3349616MathSciNetCrossRefMATH

10.

Allender, E., Holden, D., Kabanets, V.: The minimum oracle circuit size problem. Comput. Complex. 26(2), 469–496 (2017). https://doi.org/10.1007/s00037-016-0124-0MathSciNetCrossRefMATH

11.

Allender, E., Ilango, R., Vafa, N.: The non-hardness of approximating circuit size. In: van Bevern, R., Kucherov, G. (eds.) CSR 2019. LNCS, vol. 11532, pp. 13–24. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19955-5_2CrossRef

12.

Allender, E., Koucky, M., Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77, 14–40 (2010). https://doi.org/10.1016/j.jcss.2010.06.004MathSciNetCrossRefMATH

13.

Allender, E., Watanabe, O.: Kolmogorov complexity and degrees of tally sets. In: Proceedings: Third Annual Structure in Complexity Theory Conference, pp. 102–111. IEEE Computer Society (1988). https://doi.org/10.1109/SCT.1988.5269, see also [14]

14.

Allender, E., Watanabe, O.: Kolmogorov complexity and degrees of tally sets. Inf. Comput. 86(2), 160–178 (1990). https://doi.org/10.1016/0890-5401(90)90052-JMathSciNetCrossRefMATH

15.

Antunes, L., Fortnow, L., van Melkebeek, D., Vinodchandran, N.V.: Computational depth: concept and applications. Theor. Comput. Sci. 354(3), 391–404 (2006). https://doi.org/10.1016/j.tcs.2005.11.033MathSciNetCrossRefMATH

16.

Arvind, V., et al.: Reductions to sets of low information content. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 162–173. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55719-9_72. See also [17]CrossRef

17.

Arvind, V., et al.: Reductions to sets of low information content. In: Ambos-Spies, K., Homer, S., Schoning, U. (eds.) Complexity Theory: Current Research, pp. 1–46. Cambridge University Press (1993)

18.

Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 112–117 (1982). https://doi.org/10.1109/SFCS.1982.72, see also [19]

19.

Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13(4), 850–864 (1984). https://doi.org/10.1137/0213053MathSciNetCrossRefMATH

20.

Book, R.V., Lutz, J.H.: On languages with very high information content. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pp. 255–259. IEEE Computer Society (1992). https://doi.org/10.1109/SCT.1992.215400, see also [21]

21.

Book, R.V., Lutz, J.H.: On languages with very high space-bounded Kolmogorov complexity. SIAM J. Comput. 22(2), 395–402 (1993). https://doi.org/10.1137/0222029MathSciNetCrossRefMATH

22.

Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput. 31(3), 887–905 (2001). https://doi.org/10.1137/S009753979834388XMathSciNetCrossRefMATH

23.

Buhrman, H., Mayordomo, E.: An excursion to the Kolmogorov random strings. JCSS 54, 393–399 (1997). https://doi.org/10.1006/jcss.1997.1484MathSciNetCrossRefMATH

24.

Daley, R.: On the inference of optimal descriptions. Theor. Comput. Sci. 4(3), 301–319 (1977). https://doi.org/10.1016/0304-3975(77)90015-9MathSciNetCrossRefMATH

25.

Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, Heidelberg (2010). https://doi.org/10.1007/978-0-387-68441-3CrossRefMATH

26.

Gavaldà, R., Torenvliet, L., Watanabe, O., Balcázar, J.L.: Generalized Kolmogorov complexity in relativized separations (extended abstract). In: Rovan, B. (ed.) MFCS 1990. LNCS, vol. 452, pp. 269–276. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0029618CrossRef

27.

Golovnev, A., Ilango, R., Impagliazzo, R., Kabanets, V., Kolokolova, A., Tal, A.: \({\rm AC}^0[{\rm p}]\) lower bounds against MCSP via the coin problem. In: 46th International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 132, pp. 66:1–66:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.66

28.

Hemachandra, L.A., Wechsung, G.: Using randomness to characterize the complexity of computation. In: Proceedings of the IFIP 11th World Computer Congress on Information Processing 1989, pp. 281–286. North-Holland/IFIP (1989), see also [29]

29.

Hemachandra, L.A., Wechsung, G.: Kolmogorov characterizations of complexity classes. Theor. Comput. Sci. 83(2), 313–322 (1991). https://doi.org/10.1016/0304-3975(91)90282-7MathSciNetCrossRefMATH

30.

Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 247–258 (2018). https://doi.org/10.1109/FOCS.2018.00032

31.

Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: 32nd Conference on Computational Complexity, CCC. LIPIcs, vol. 79, pp. 7:1–7:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.CCC.2017.7

32.

Hitchcock, J.M., Pavan, A.: On the NP-completeness of the minimum circuit size problem. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). LIPIcs, vol. 45, pp. 236–245. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). https://doi.org/10.4230/LIPIcs.FSTTCS.2015.236

33.

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)MATH

34.

Ilango, R.: Approaching MCSP from above and below: Hardness for a conditional variant and AC\(^0[p]\). In: 11th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 151, pp. 34:1–34:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.34

35.

Ilango, R., Loff, B., Oliveira, I.C.: NP-hardness of minimizing circuits and communication (2019, manuscript)

36.

Kabanets, V., Cai, J.Y.: Circuit minimization problem. In: ACM Symposium on Theory of Computing (STOC), pp. 73–79 (2000). https://doi.org/10.1145/335305.335314

37.

Ko, K.: On the notion of infinite pseudorandom sequences. Theor. Comput. Sci. 48(3), 9–33 (1986). https://doi.org/10.1016/0304-3975(86)90081-2MathSciNetCrossRefMATH

38.

Ko, K.: On the complexity of learning minimum time-bounded Turing machines. In: Proceedings of the Third Annual Workshop on Computational Learning Theory, (COLT), pp. 82–96 (1990), see also [39]

39.

Ko, K.: On the complexity of learning minimum time-bounded Turing machines. SIAM J. Comput. 20(5), 962–986 (1991). https://doi.org/10.1137/0220059MathSciNetCrossRefMATH

40.

Ko, K.-I., Orponen, P., Schöning, U., Watanabe, O.: What is a hard instance of a computational problem? In: Selman, A.L. (ed.) Structure in Complexity Theory. LNCS, vol. 223, pp. 197–217. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-16486-3_99. See also [51]CrossRef

41.

Kolmogorov, A.N.: Three approaches to the quantitative definition ofinformation’. Probl. Inf. Transm. 1(1), 1–7 (1965)MathSciNet

42.

Levin, L.: Universal search problems. Probl. Inf. Transm. 9, 265–266 (1973)

43.

Levin, L.A.: Randomness conservation inequalities; information and independence in mathematical theories. Inf. Control 61(1), 15–37 (1984). https://doi.org/10.1016/S0019-9958(84)80060-lMathSciNetCrossRefMATH

44.

Li, M., Vitanyi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science, 4th edn. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-11298-1CrossRefMATH

45.

McKay, D.M., Murray, C.D., Williams, R.R.: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1215–1225 (2019). https://doi.org/10.1145/3313276.3316396

46.

Meyer, A., McCreight, E.: Computationally complex and pseudo-random zero-one valued functions. In: Theory of Machines and Computations, pp. 19–42. Elsevier (1971)

47.

Murray, C., Williams, R.: On the (non) NP-hardness of computing circuit complexity. Theory Comput. 13(4), 1–22 (2017). https://doi.org/10.4086/toc.2017.v013a004MathSciNetCrossRef

48.

Oliveira, I., Santhanam, R.: Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In: 32nd Conference on Computational Complexity, CCC. LIPIcs, vol. 79, pp. 18:1–18:49. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.CCC.2017.18

49.

Oliveira, I.C., Pich, J., Santhanam, R.: Hardness magnification near state-of-the-art lower bounds. In: 34th Computational Complexity Conference (CCC). LIPIcs, vol. 137, pp. 27:1–27:29. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.CCC.2019.27

50.

Oliveira, I.C., Santhanam, R.: Hardness magnification for natural problems. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 65–76 (2018). https://doi.org/10.1109/FOCS.2018.00016

51.

Orponen, P., Ko, K., Schoning, U., Watanabe, O.: Instance complexity. J. ACM 41(1), 96–121 (1994). https://doi.org/10.1145/174644.174648MathSciNetCrossRefMATH

52.

Paul, W.J., Seiferas, J.I., Simon, J.: An information-theoretic approach to time bounds for on-line computation (preliminary version). In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC 1980, pp. 357–367. ACM, New York (1980). https://doi.org/10.1145/800141.804685, see also [53]

53.

Paul, W.J., Seiferas, J.I., Simon, J.: An information-theoretic approach to time bounds for on-line computation. J. Comput. Syst. Sci. 23(2), 108–126 (1981). https://doi.org/10.1016/0022-0000(81)90009-XMathSciNetCrossRefMATH

54.

Peterson, G.L.: Succinct representation, random strings, and complexity classes. In: 21st Annual Symposium on Foundations of Computer Science (FOCS), pp. 86–95 (1980). https://doi.org/10.1109/SFCS.1980.42

55.

Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965–984 (1988). https://doi.org/10.1145/48014.63140MathSciNetCrossRefMATH

56.

Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM 40(1), 95–142 (1993). https://doi.org/10.1145/138027.138042MathSciNetCrossRefMATH

57.

Rudow, M.: Discrete logarithm and minimum circuit size. Inf. Process. Lett. 128, 1–4 (2017). https://doi.org/10.1016/j.ipl.2017.07.005MathSciNetCrossRefMATH

58.

Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 330–335 (1983). https://doi.org/10.1145/800061.808762

59.

Trakhtenbrot, B.A.: A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Ann. Hist. Comput. 6(4), 384–400 (1984)CrossRef

60.

Watanabe, O.: Kolmogorov Complexity and Computational Complexity, 1st edn. Springer, Heidelberg (2012)MATH

61.

Wilber, R.E.: Randomness and the density of hard problems. In: 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 335–342 (1983). https://doi.org/10.1109/SFCS.1983.49

62.

Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 80–91 (1982). https://doi.org/10.1109/SFCS.1982.45

Title: Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
Author: Eric Allender
Publisher: Springer International Publishing
Book: Complexity and Approximation
Print ISBN: 978-3-030-41671-3

Electronic ISBN: 978-3-030-41672-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-41672-0_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner