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
    0 references
    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

    Identifiers