Independence results about context-free languages and lower bounds (Q1071500)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Independence results about context-free languages and lower bounds
scientific article

    Statements

    Independence results about context-free languages and lower bounds (English)
    0 references
    0 references
    1985
    0 references
    For every axiomatizable, sound formal system F there exist instances about context-free languages, lower bounds of computation and recursive oracles A for which \(NP^ A\neq P^ A\) that are not provable in F for every recursive representation of these problems.
    0 references
    provability
    0 references
    recursive oracles
    0 references

    Identifiers