Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
The polynomially exponential time restrained analytical hierarchy - MaRDI portal

The polynomially exponential time restrained analytical hierarchy (Q1337640)

From MaRDI portal





scientific article; zbMATH DE number 683608
Language Label Description Also known as
English
The polynomially exponential time restrained analytical hierarchy
scientific article; zbMATH DE number 683608

    Statements

    The polynomially exponential time restrained analytical hierarchy (English)
    0 references
    0 references
    7 June 1995
    0 references
    The author defines a \(p\)-analytical hierarchy of relations \(\Sigma^{1,p} [n]\) and \(\Pi^{1,p} [n]\) making some mistakes through carelessness in definitions. A series of simple properties of the hierarchy are given generalizing those of the well-known analytical hierarchy. Then the author shows that there exists a (recursive) oracle \(A\) such that the sentence `\(\Sigma^{1,p} [n] [A]= \Sigma^{1,p} [n+1] [A]\)' is neither provable nor disprovable in ZF.
    0 references
    deterministic Turing machine
    0 references
    polynomial time
    0 references
    polynomially exponential time
    0 references
    polynomially analytical hierarchy
    0 references
    oracle
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references