Sage Journals: Discover world-class research

Abstract

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform ${TC}^{0}$ circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (initially studied by Maciel and Thérien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy, and we answer a question posed by Yap.

Keywords

Threshold circuits counting hierarchy algebraic numbers

Get full access to this article

View all access options for this article.

References

Adamczewski and

Bugeaud, On the complexity of algebraic numbers I. Expansions in integer bases, Annals of Mathematics (2007), 547–565. doi:10.4007/annals.2007.165.547.

Adamczewski,

Bugeaud and

Luca, Sur la complexité des nombres algébriques, Comptes Rendus Mathematique 339(1) (2004), 11–14. doi:10.1016/j.crma.2004.04.012.

Adamczewski,

Cassaigne and

Le Gonidec, On the computational complexity of algebraic numbers: The Hartmanis–Stearns problem revisited, Transactions of the American Mathematical Society 373(5) (2020), 3085–3115. doi:10.1090/tran/7915.

Agrawal,

Allender and

Datta, On TC⁰, AC⁰, and arithmetic circuits, Journal of Computer and System Sciences 60(2) (2000), 395–421. doi:10.1006/jcss.1999.1675.

Allender, The permanent requires large uniform threshold circuits, Chicago J. Theor. Comput. Sci. 1999 (1999). doi:10.4086/cjtcs.1999.007.

Allender, The division breakthroughs, in: Current Trends in Theoretical Computer Science, the Challenge of the New Century, Vol. 1: Algorithms and Complexity,

Paun,

Rozenberg and

Salomaa, eds, World Scientific, 2004, pp. 147–164. doi:10.1142/9789812562494_0011.

Allender,

Balaji and

Datta, Low-depth uniform threshold circuits and the bit-complexity of straight line programs, in: Mathematical Foundations of Computer Science (MFCS), Vol. 8635, Springer, 2014, pp. 13–24.

Allender,

Bürgisser,

Kjeldgaard-Pedersen and

P.B.

Miltersen, On the complexity of numerical analysis, SIAM J. Comput. 38(5) (2009), 1987–2006. doi:10.1137/070697926.

Allender,

M.E.

Saks and

I.E.

Shparlinski, A lower bound for primality, Journal of Computer and System Sciences 62(2) (2001), 356–366. doi:10.1006/jcss.2000.1725.

10.

Allender and

Schnorr, The complexity of the BitSLP problem, 2005, Unpublished Manuscript.

11.

J.-P.

Allouche and

Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003. ISBN 0521823323.

12.

Arora and

Barak, Computational Complexity: A Modern Approach, Vol. 1, Cambridge University Press, 2009.

13.

Bailey,

Borwein and

Plouffe, On the rapid computation of various polylogarithmic constants, Mathematics of Computation 66(218) (1997), 903–913. doi:10.1090/S0025-5718-97-00856-9.

14.

D.H.

Bailey, A Compendium of BBP-Type Formulas for Mathematical Constants, Report, Lawrence, Berkeley National Laboratory, Berkeley, CA, USA, 2017.

15.

D.A.M.

Barrington,

K.J.

Compton,

Straubing and

Thérien, Regular languages in NC1, Journal of Computer and System Sciences 44(3) (1992), 478–499. doi:10.1016/0022-0000(92)90014-A.

16.

D.A.M.

Barrington and

J.C.

Corbett, A note on some languages in uniform ACC⁰, Theor. Comput. Sci. 78(2) (1991), 357–362. doi:10.1016/0304-3975(91)90357-8.

17.

P.W.

Beame,

S.A.

Cook and

H.J.

Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing 15 (1986), 994–1003. doi:10.1137/0215070.

18.

R.B.

Boppana and

J.C.

Lagarias, One-way functions and circuit complexity, Information and Computation 74(3) (1987), 226–240. doi:10.1016/0890-5401(87)90022-8.

19.

J.M.

Borwein and

P.B.

Borwein, Pi and the AGM: A Study in the Analytic Number Theory and Computational Complexity, Wiley-Interscience, 1987.

20.

Brattka and

Hertling, Handbook of Computability and Complexity in Analysis, Springer, 2021. doi:10.1007/978-3-030-59234-9.

21.

Caussinus,

McKenzie,

Thérien and

Vollmer, Nondeterministic

{NC}^{1}

computation, Journal of Computer and System Sciences 57 (1998), 200–212. doi:10.1006/jcss.1998.1588.

22.

Chiu,

G.I.

Davida and

B.E.

Litow, Division in logspace-uniform NC¹, RAIRO Theoretical Informatics and Applications 35(3) (2001), 259–275. doi:10.1051/ita:2001119.

23.

Chonev,

Ouaknine and

Worrell, The orbit problem in higher dimensions, in: Proc. Symposium on Theory of Computing Conference (STOC), ACM, 2013, pp. 941–950. doi:10.1145/2488608.2488728.

24.

K.J.

Compton and

Straubing, Characterizations of regular languages in low level complexity classes, in: Current Trends in Theoretical Computer Science, Entering the 21th Century,

Paun,

Rozenberg and

Salomaa, eds, World Scientific, 2001, pp. 235–246.

25.

Datta and

Pratap, Computing bits of algebraic numbers, in: Proc. 9th Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science, Vol. 7287, Springer, 2012, pp. 189–201. doi:10.1007/978-3-642-29952-0_22.

26.

Dietz,

Macarie and

Seiferas, Bits and relative order from residues, space efficiently, Information Processing Letters 50(3) (1994), 123–127. doi:10.1016/0020-0190(94)00021-2.

27.

R.G.

Downey,

D.R.

Hirschfeldt,

Nies and

Stephan, Trivial reals, in: Proceedings of the 7th and 8th Asian Logic Conferences, World Scientific, 2003, pp. 103–131. doi:10.1142/9789812705815_0005.

28.

Edalat and

P.M.

Potts, A new representation for exact real numbers, Electronic Notes in Theoretical Computer Science 6 (1997), 119–132. doi:10.1016/S1571-0661(05)80166-5.

29.

Etessami and

Yannakakis, On the complexity of Nash equilibria and other fixed points, SIAM J. Comput. 39(6) (2010), 2531–2597. doi:10.1137/080720826.

30.

Etessami Probability, Recursion, Games, and Fixed Points, 2013, Talk presented at Horizons in TCS: A Celebration of Mihalis Yannakakis’ 60th Birthday.

31.

J.D.

Faires and

R.L.

Burden, Numerical Methods, PWS Publishing, Boston, 1993. ISBN 0-534-93136-7.

32.

Freivalds, Hartmanis–Stearns conjecture on real time and transcendence, in: Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012, Dedicated to Cristian S. Calude on the Occasion of His 60th Birthday, Revised Selected and Invited Papers,

M.J.

Dinneen,

Khoussainov and

Nies, eds, Lecture Notes in Computer Science, Vol. 7160, Springer, 2012, pp. 105–119. doi:10.1007/978-3-642-27654-5_9.

33.

Galby,

Ouaknine and

Worrell, On matrix powering in low dimensions, in: Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Vol. 30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015, pp. 329–340. doi:10.4230/LIPIcs.STACS.2015.329.

34.

Goldmann and

Karpinski, Simulating threshold circuits by majority circuits, SIAM J. Comput. 27(1) (1998), 230–246. doi:10.1137/S0097539794274519.

35.

Hartmanis and

R.E.

Stearns, On the computational complexity of algorithms, Transactions of the American Mathematical Society 117 (1965), 285–306. doi:10.1090/S0002-9947-1965-0170805-7.

36.

Healy and

Viola, Constant-depth circuits for arithmetic in finite fields of characteristic two, in: Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 3884, Springer, 2006, pp. 672–683. doi:10.1007/11672142_55.

37.

Hesse,

Allender and

D.A.M.

Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences 65 (2002), 695–716. doi:10.1016/S0022-0000(02)00025-9.

38.

Hirvensalo,

Karhumäki and

Rabinovich, Computing partial information out of intractable: Powers of algebraic numbers as an example, Journal of Number Theory 130 (2010), 232–253. doi:10.1016/j.jnt.2009.08.009.

39.

Jeřábek, Root finding with threshold circuits, Theoretical Computer Science 462 (2012), 59–69. doi:10.1016/j.tcs.2012.09.001.

40.

Jindal and

Saranurak, Subtraction makes computing integers faster, 2012, CoRR arXiv:1212.2549.

41.

Kayal and

Saha, On the sum of square roots of polynomials and related problems, ACM Transactions on Computation Theory 4(4) (2012), 9:1–9:15. doi:10.1145/2382559.2382560.

42.

Ko, On the definitions of some complexity classes of real numbers, Mathematical Systems Theory 16(2) (1983), 95–109. doi:10.1007/BF01744572.

43.

Ko and

Friedman, Computational complexity of real functions, Theor. Comput. Sci. 20 (1982), 323–352. doi:10.1016/S0304-3975(82)80003-0.

44.

Koiran and

Perifel, The complexity of two problems on arithmetic circuits, Theor. Comput. Sci. 389(1–2) (2007), 172–181. doi:10.1016/j.tcs.2007.08.008.

45.

Koiran and

Perifel, Interpolation in valiant’s theory, Computational Complexity 20(1) (2011), 1–20. doi:10.1007/s00037-011-0002-8.

46.

Lechner,

Ouaknine and

Worrell, On the complexity of linear arithmetic with divisibility, in: 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Society, 2015, pp. 667–676. doi:10.1109/LICS.2015.67.

47.

R.J.

Lipton and

K.W.

Regan, People, Problems, and Proofs – Essays from Gödel’s Lost Letter: 2010, Springer, 2013. doi:10.1007/978-3-642-41422-0.

48.

Maciel and

Thérien, Threshold circuits of small majority-depth, Inf. Comput. 146(1) (1998), 55–83. doi:10.1006/inco.1998.2732.

49.

Mereghetti and

Palano, Threshold circuits for iterated matrix product and powering, ITA 34(1) (2000), 39–46.

50.

J.S.

Miller, Every 2-random real is Kolmogorov random, Journal of Symbolic Logic 69(3) (2004), 907–913. doi:10.2178/jsl/1096901774.

51.

C.D.

Murray and

R.R.

Williams, Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma, SIAM Journal on Computing 49(5) (2020). doi:10.1137/18M1195887.

52.

Nakanishi and

Villagra, Computational Complexity of Space-Bounded Real Numbers, 2018, CoRR, arXiv:1805.02572.

53.

Nies,

Stephan and

S.A.

Terwijn, Randomness, relativization and Turing degrees, The Journal of Symbolic Logic 70(2) (2005), 515–535. doi:10.2178/jsl/1120224726.

54.

Ouaknine and

Worrell, Positivity problems for low-order linear recurrence sequences, in: Proceedings of the Twenty-Fifth Annual ACM-Siam Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, pp. 366–379.

55.

Ouaknine and

Worrell, On the positivity problem for simple linear recurrence sequences, in: Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part II, Lecture Notes in Computer Science, Vol. 8573, Springer, 2014, pp. 318–329. doi:10.1007/978-3-662-43951-7_27.

56.

P.M.

Potts, Efficient on-line computation of real functions using exact floating point, in: Manuscript, Dept. of Computing, Imperial College, London, 1997.

57.

P.M.

Potts, Exact Real Arithmetic using Möbius Transformations, PhD thesis, Imperial College, University of London, 1999.

58.

A.A.

Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Matematicheskie Zametki 41 (1987), 598–607, In Russian. English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:333–338, 1987.

59.

J.H.

Reif and

S.R.

Tate, On threshold circuits and polynomial computation, SIAM J. Comput. 21(5) (1992), 896–908, citeseer.nj.nec.com/reif87threshold.html . doi:10.1137/0221053.

60.

K.F.

Roth, Rational approximations to algebraic numbers, Mathematika. A Journal of Pure and Applied Mathematics 2 (1955), 1–20.

61.

A.A.

Sherstov, Powering requires threshold depth 3, Inf. Process. Lett. 102(2–3) (2007), 104–107. doi:10.1016/j.ipl.2006.11.003.

62.

A.B.

Shidlovskii, Transcendental Numbers, de Gruyter, New York, 1989.

63.

K.-Y.

Siu and

V.P.

Roychowdhury, On optimal depth threshold circuits for multiplication and related problems, SIAM J. Discrete Math. 7(2) (1994), 284–292. doi:10.1137/S0895480192228619.

64.

Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proceedings, 19th ACM Symposium on Theory of Computing, 1987, pp. 77–82.

65.

Stark, Introduction to Numerical Methods, Macmillan, 1970.

66.

Tiwari, A problem that is easier to solve on the unit-cost algebraic RAM, J. Complexity 8(4) (1992), 393–397. doi:10.1016/0885-064X(92)90003-T.

67.

Toda, PP is as hard as the polynomial time hierarchy, SIAM J. Comput. 20 (1991), 865–877. doi:10.1137/0220053.

68.

A.M.

Turing, On computable numbers, with an application to the entscheidungsproblem, Proc. London Math. Soc. 2(42) (1936), 230–265.

69.

Vollmer, Introduction to Circuit Complexity, Springer-Verlag, 1999.

70.

Wegener, Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions, Inf. Process. Lett. 46(2) (1993), 85–87. doi:10.1016/0020-0190(93)90202-K.

71.

Weihrauch, Computable Analysis – an Introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer, 2000. doi:10.1007/978-3-642-56999-9.

72.

Yap, Fundamental Problems in Algorithmic Algebra, Oxford University Press, 2000.

73.

Yap, Pi is in Log Space, 2010, manuscript available at: https://cs.nyu.edu/exact/doc/pi-log.pdf.

74.

Yu and

Ko, On logarithmic-space computable real numbers, Theoretical Computer Science 469 (2013), 127–133. doi:10.1016/j.tcs.2012.10.004.

75.

Yu,

Ding and

Downey, The Kolmogorov complexity of random reals, Annals of Pure and Applied Logic 129(1–3) (2004), 163–180. doi:10.1016/j.apal.2004.01.006.

76.

Zeilberger and

Zudilin, The irrationality measure of π is at most 7.103205334137…, Moscow Journal of Combinatorics and Number Theory 9(4) (2020), 407–419. doi:10.2140/moscow.2020.9.407.

On the complexity of algebraic numbers,and the bit-complexity of straight-line programs 1

Abstract

Keywords

Get full access to this article

References