Bounded arithmetic for NC, ALogTIME, L and NL (Q1192345)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounded arithmetic for NC, ALogTIME, L and NL |
scientific article |
Statements
Bounded arithmetic for NC, ALogTIME, L and NL (English)
0 references
27 September 1992
0 references
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.
0 references
bounded arithmetic
0 references
definable functions
0 references
complexity classes
0 references
fragment TNC of bounded first-order arithmetic
0 references
parallel complexity class NC
0 references
polylogarithmic time
0 references
polynomial number of processors
0 references
parallel random- access machine
0 references
fragments of bounded second-order arithmetic
0 references
definable relations
0 references
ALogTIME
0 references
NL
0 references
L
0 references