zbMATH — the first resource for mathematics

Bounded arithmetic for NC, ALogTIME, L and NL. (English) Zbl 0772.03028
The authors define theories of bounded arithmetic whose definable functions or relations are exactly those in certain complexity classes. They define a fragment TNC of bounded first-order arithmetic and prove that functions in the parallel complexity class NC are exactly those functions which are \(\Sigma^ b_ 1\)-definable in TNC. The class NC consists of all functions computable in polylogarithmic time with a polynomial number of processors on a parallel random-access machine. Then the authors define fragments of bounded second-order arithmetic such that suitably definable relations are, respectively, in the complexity classes ALogTIME, NL and L.

03F30 First-order arithmetic and fragments
03D15 Complexity of computation (including implicit computational complexity)
03F35 Second- and higher-order arithmetic and fragments
Full Text: DOI
[1] Allen, B., Arithmetizing uniform NC, Ann. pure appl. logic, 53, 1, 1-50, (1991) · Zbl 0741.03019
[2] Baase, S., Computer algorithms, () · Zbl 0407.68044
[3] Borodin, A., On relating time and space to size and depth, SIAM J. comput., 6, 733-744, (1977) · Zbl 0366.68039
[4] Buss, S.R., Bounded arithmetic, (), Lecture Notes · Zbl 0654.03043
[5] Clote, P.G., A sequential programming language for parallel complexity classes, ()
[6] Clote, P., Sequential, machine independent characterizations of the parallel complexity classes alogtime, AC^k, nck, and NC, (), 49-70 · Zbl 0765.68034
[7] Clote, P.G.; Takeuti, G., Exponential time and bounded arithmetic, (), 125-143, Lecture Notes in Comput. Sci. · Zbl 0772.03028
[8] Cobham, A., The intrinsic computational difficulty of functions, (), 24-30
[9] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[10] Cook, S.A.; Urquhart, A., Functional interpretations of feasibly constructive arithmetic, () · Zbl 0776.03028
[11] Girard, J.-Y., Proof theory and logical complexity, (), Lecture Notes
[12] Goldschlager, L., Synchronous parallel computation, ()
[13] Immermann, N., Languages that capture complexity classes, SIAM J. comput., 16, 4, 760-778, (1987) · Zbl 0634.68034
[14] R. Kaye, Parameter-free induction schemas, J. Symbolic Logic, to appear. · Zbl 0678.03025
[15] Lind, J.C., Computing in logarithmic space, ()
[16] Moitra, A.; Iyengar, S.S., Parallel algorithms for some computational problems, () · Zbl 0637.68037
[17] Rose, H.E., Subrecursion-functions and hierarchies, () · Zbl 0539.03018
[18] Ruzzo, W.L., On uniform circuit complexity, J. comput. system sci., 22, 365-383, (1979) · Zbl 0462.68013
[19] Takeuti, G., Proof theory, () · Zbl 0182.01202
[20] Takeuti, G., Sharply bounded arithmetic and the function a ∸ 1, (), 281-288
[21] Wilkie, A.J.; Wilmers, G., Personal communication, (1985)
[22] Proc. 20th IEEE symp. on the foundations of computer science, On simultaneous resource bounds, 307-311, (1979)
[23] Proc. 23rd IEEE symp. on foundations of computer science, 1-13, (1983)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.